#include<bits/stdc++.h>
using namespace std;

int T,n,m,k;

const int inf=1e8;

const int maxn = 1e5+1;

int ans[maxn];

int u,v;

int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d", &T);
    for(int i=0;i!=T;i++)
    {
        memset(ans, -1, sizeof(ans));
        scanf("%d %d %d", &n, &m, &k);        
        ans[k]=0;
        for(int j=0;j!=m;j++)
        {
            scanf("%d %d", &u, &v);
            if(ans[u]==-1&&ans[v]==-1)continue;
            int uu=inf, uv=inf, vu=inf, vv=inf;
            if(ans[u]>=0)
            {
                if(ans[v]>=0)uv=min(ans[v]+1, ans[u]);    
                else uv=ans[u];
                uu = ans[u]+1;
            }
            if(ans[v]>=0)
            {
                if(ans[u]>=0)vu = min(ans[u]+1, ans[v]);
                else vu = ans[v];
                vv=ans[v]+1;
            }
            
            ans[u]=inf;
            ans[u]=min(ans[u], uu);
            ans[u]=min(ans[u], vu);
            
            ans[v]=inf;
            ans[v]=min(ans[v], uv);
            ans[v]=min(ans[v], vv);
        }
        for(int j=1;j<=n;j++)
        {
            if(j!=1)printf(" ");
            printf("%d", ans[j]);
        }
        printf("\n");
    }
    return 0;
}