ACM 20ケチな国Java

けちな国にはNつの都市があり、このNつの都市の間にはN-1本の道だけがこのNつの都市をつなぐと描かれています.今、トムはS番都市にいます.彼はこの国の地図を持っています.もし自分がT番都市を見学するなら、通らなければならない前の都市は何番都市ですか(繰り返しの道を歩かないと仮定します).
入力
1行目入力整数Mは、テストデータ共有M(1<=M<=5)のグループ
各試験データの最初の行には、正の整数N(1<=N<=10000000)と正の整数S(1<=S<=10000000)が入力され、Nは都市の総数を表し、Sは見学者の所在都市の番号を表す
その後のN−1行は、各行に2つの正の整数a,b(1<=a,b<=N)があり、a番目の都市とb番目の都市の間に1つの道路が連通していることを示す.
しゅつりょく
各試験データは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.util.concurrent.ConcurrentLinkedQueue;

/**
 *           ：1000 ms |     ：65535 KB   ：3   
 *           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
 * 
 * @author daniel
 * @email [email protected]
 * @time 2016-5-12   2:53:46
 */
public class Main {
	public static void main(String[] args) {
		//       
		Scanner in = new Scanner(System.in);
		int M = in.nextInt();
		int[] N = new int[M];
		int[] S = new int[M];
		Queue result = new ConcurrentLinkedQueue();

		for (int i = 0; i < M; i++) {
			N[i] = in.nextInt();
			S[i] = in.nextInt();
			int[] a = new int[N[i] - 1];
			int[] b = new int[N[i] - 1];
			for (int j = 0; j < N[i] - 1; j++) {
				a[j] = in.nextInt();
				b[j] = in.nextInt();
			}
			//    i   （ b[l]=i）  a[l]    result
			for (int k = 1; k <= N[i]; k++) {
				if (S[i] == k)
					result.add(-1);
				for (int l = 0; l < N[i] - 1; l++) {
					if (b[l] == k) {
						result.add(a[l]);
						break;
					}
				}
			}
		}
		//   
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N[i]; j++) {
				int num = result.poll();
				System.out.print(num + " ");
			}

		}
	}
}