-----------------------------------------
n-1条边的无向连通图是一棵树，又因为树上两点之间的路径是唯一的，所以解是唯一的。（注意并不一定是二叉树，所以最好采用存储图的方式存储树，我使用的是邻接表）
这个时候只需要考虑如何求解两点间的路径呢？遍历就可以了。
但是应该如何遍历呢？比较容易想到的办法是分别从每个点计算到S点的路径，既然它们的终点相同，那为什么不逆向一下干脆从S点向这些点出发呢？
所以现在问题就转化为了从S点出发遍历树，OK，这个问题就比较简单了，只需要在即将到达目的地之前记录一下就可以了。
对了，还需要注意一下的是猜测南阳OJ的JDK编译级别应该是<1.7的，因为使用new ArrayList<>()新特性的时候报语法错误了，不加即可，反正也会被擦除的。
AC代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in);
int times=sc.nextInt();
while(times-->0){
int n=sc.nextInt();
int s=sc.nextInt()-1; tree=new ArrayList[n];
for(int i=0;i<tree.length;i++) tree[i]=new ArrayList();
visited=new boolean[n];
must=new int[n]; for(int i=1;i<n;i++){
int v=sc.nextInt()-1;
int u=sc.nextInt()-1;
tree[v].add(u);
tree[u].add(v);
} must[s]=-1;
dfs(s); for(int i=0;i<must.length;i++){
System.out.print(must[i]+" ");
}
System.out.println();
} } private static List<Integer> tree[];
private static boolean visited[];
private static int must[]; public static void dfs(int i){
visited[i]=true;
for(Integer next:tree[i]){
if(visited[next]) continue;
must[next]=i+1;
dfs(next);
}
} }