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

const int maxl=3e5+10;

int n,m,k,cnt,tot,cas,ans;
int a[maxl],b[maxl],au[maxl],av[maxl],dp[maxl];
char s[maxl];


inline void prework()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        dp[i]=-1;
    dp[k]=0;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int yu=dp[u],yv=dp[v];
        if(yu>=0)
            dp[u]=yu+1;
        if(yv>=0)
            dp[v]=yv+1;
        if(yu>=0)
        {
            if(yv<0)
                dp[v]=yu;
            else
                dp[v]=min(dp[v],yu);
        }
        if(yv>=0)
        {
            if(yu<0)
                dp[u]=yv;
            else
                dp[u]=min(dp[u],yv);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",dp[i]," \n"[i==n]);
}

inline void mainwork()
{
    
}

inline void print()
{
    
}

int main()
{
    int t=1;
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}