C++ :

#include <stdio.h>
#include <stdlib.h>
typedef struct city{
  int id;
  city *adj;
  int last;
}city;
city clist[100001];
int last,s;
void initclist(int n){
  for(int i=1;i<=n-1;i++){
    clist[i].id=i;
    clist[i].adj=NULL;
  }
}
void add(int a,int b){
  city *tmp=(city*)malloc(sizeof(city));
  tmp->id=b;
  tmp->adj=clist[a].adj;
  clist[a].adj=tmp;
}
void dfs(int cid,int lid){
  city *cur=&clist[cid];
  cur->last=lid;
  while(cur->adj){
    if(cur->adj->id!=lid)
      dfs(cur->adj->id,cid);
    cur=cur->adj;
  }
}
int main(){
  int m,n;
  scanf("%d",&m);
  while(m--){
    int a,b,last;
    scanf("%d %d",&n,&s);
    initclist(n);
    for(int i=1;i<=n-1;i++){
      scanf("%d %d",&a,&b);
      add(a,b);
      add(b,a);
    }
    dfs(s,-1);
    for(int i=1;i<=n;i++)
      printf("%d ",clist[i].last);
    printf("\n");
  }
}