#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000;
int n,m,k,dp[MAXN+5];
int main()
{
    int T;
    scanf("%d",&T);
    for(int tmn=1;tmn<=T;tmn++)
    {
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            dp[i]=MAXN*2;
        dp[k]=0;
        for(int i=1;i<=m;i++)
        {
            int u,v,tmp1,tmp2;
            scanf("%d %d",&u,&v);
            tmp1=dp[u],tmp2=dp[v];
            if(u==v)
                continue;
            dp[u]=min(tmp2,tmp1+1);
            dp[v]=min(tmp1,tmp2+1);
        }
        bool fir=true;
        for(int i=1;i<=n;i++)
        {
            if(!fir)
                printf(" ");
            fir=false;
            if(dp[i]==MAXN*2)
                printf("-1");
            else
                printf("%d",dp[i]);
        }
        printf("\n");
    }
    return 0;
}