#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5+5;
int tes,n,m,k,f[M];
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)f[i]=-1;
    f[k]=0;
    for(int i=1,x,y,t1,t2;i<=m;i++){
        scanf("%d%d",&x,&y);
        if((~f[x])&&(~f[y])){
            t1=min(f[x]+1,f[y]);
            t2=min(f[y]+1,f[x]);
        }
        else if((~f[x])&&(!~f[y])){
            t1=f[x]+1;
            t2=f[x];
        }
        else if((!~f[x])&&(~f[y])){
            t1=f[y];
            t2=f[y]+1;
        }
        else t1=t2=-1;
        f[x]=t1,f[y]=t2;
    }
    for(int i=1;i<n;i++)printf("%d ",f[i]);
    printf("%d\n",f[n]);
}
int main()
{
    scanf("%d",&tes);
    while(tes--)solve();
    return 0;
}