java 图的标题，超时啊帮忙看看

java 图的题目，超时啊，帮忙看看啊
http://acm.nyist.net/JudgeOnline/problem.php?pid=20


描述
在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。
输入
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。
输出
每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1）
样例输入
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7
样例输出
-1 1 10 10 9 8 3 1 1 8



import java.util.*;
import java.io.*;

public class Main {
public static void main(String[] args) {
int m, n, s, a, b;
Scanner scanner = new Scanner(System.in);
List<Integer> list = new ArrayList<Integer>();
Map<Integer, ArrayList> map = new HashMap<Integer, ArrayList>();

m = scanner.nextInt();
for (int i = 0; i < m; i++) {
n = scanner.nextInt();
s = scanner.nextInt();
// 输入键值，构建图
for (int j = 0; j < n - 1; j++) {
a = scanner.nextInt();
b = scanner.nextInt();

if (!map.containsKey(a))
map.put(a, new ArrayList<Integer>(b));

if (map.containsKey(a))
map.get(a).add(b);
}

// list用于保存键
list.clear();
list.addAll(map.keySet());

// 对图进行遍历
for (int k = 1; k <= n; k++) {
if (s == k) {
System.out.print(-1 + " ");
continue;
}

for (int j = 0; j < map.size(); j++)
if (map.get(list.get(j)).contains(k)) {
System.out.print(list.get(j) + " ");
break;
}
}
System.out.println();
}

}
}


水平太低，第一次发帖，别沉了，帮帮忙啊
------解决方案--------------------
不一定是你的程序问题。有可能是它网站问题。有人说过这个
------解决方案--------------------
兄弟，没问题啊。有图有真相。