#include <iostream>

#include <stdio.h>

#include <vector>

using namespace std;

vector<int>a[];

int b[],n,s;

void dfs(int x,int y){

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

        if (a[x][i] != y)

            dfs(a[x][i],b[a[x][i]]=x);

        return;

}

int main(){

    int M,x,y;

    scanf("%d",&M);

    while (M--){

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

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

            a[i].clear();

        }

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

            scanf("%d%d",&x,&y);

            a[x].push_back(y); //相当二维数组

            a[y].push_back(x);

        }

        b[s] = -;//与S相等则为-1

        dfs(s,-);

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

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

        printf("\n");

    }

    return ;

}