#include<stdio.h>

 #include<iostream>

 #include<vector>

 #include<string.h>

 using namespace std;

 vector<int>v[];

 int pre[];

 void func(int x)

 {

     int i;

     for(i=;i<v[x].size();i++)

     {

         if(pre[v[x][i]])

         continue;

         pre[v[x][i]]=x;

         func(v[x][i]);

     }

 }

 int main()

 {

     int m;

     scanf("%d",&m);

     while(m--)

     {

         int n,s,i,j,a,b;

         scanf("%d %d",&n,&s);

         memset(v,,sizeof(v));

         memset(pre,,sizeof(pre));

         for(i=;i<n-;i++)

         {

             scanf("%d %d",&a,&b);

             v[a].push_back(b);

             v[b].push_back(a);

         }

         pre[s]=-;

         func(s);

         for(i=;i<n;i++)

         printf("%d ",pre[i]);

         printf("%d\n",pre[n]);

     }

     return ;

 }