#include<stdio.h> #include<string.h> #define N 110000 struct node { int u,v,next; }bian[N*2]; int head[N],yong,pre[N]; void addedge(int u,int v) { bian[yong].u=u; bian[yong].v=v; bian[yong].next=head[u]; head[u]=yong++; } int visit[N]; void dfs(int u) { visit[u]=1; int i; for(i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(!visit[v]) { dfs(v); pre[v]=u; } } return ; } int main() { int t,n,s,i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&s); memset(head,-1,sizeof(head)); yong=0; for(i=1;i<n;i++) { scanf("%d%d",&j,&k); addedge(j,k); addedge(k,j); } pre[s]=-1; memset(visit,0,sizeof(visit)); dfs(s); for(i=1;i<n;i++) printf("%d ",pre[i]); printf("%d ",pre[n]); } return 0; }