#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
using namespace std;
const int N=100005;
int n,m,k;
int f[N];
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) f[i]=(i==k?0:1<<30);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        int vx=f[x],vy=f[y];
        f[x]=min(vy,vx+1);
        f[y]=min(vx,vy+1);
    }
    for (int i=1;i<=n;i++)
        printf("%d%c",f[i]>=(1<<20)?-1:f[i],i==n?'\n':' ');
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--) solve();
}