#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
typedef double db;
typedef long double ldb;
typedef vector <int> vi;
typedef vector <ll> vl;
struct pii { int x,y; };
struct pll { ll  x,y; };
typedef vector <pii> vii;
typedef vector <pll> vll;
#define pb push_back
const ll MOD = 998244353;
const int N = 150005;
inline int lowbit(int x) {return x&(-x);}
ll getgcd(ll x,ll y) {return (y==0) ? x : getgcd(y,x%y);}
ll power(ll x,ll mi,ll mod = MOD)
{
    ll s1=1LL,s2=x%mod,m=mi;
    for (;m;m>>=1) {if (m&1) s1=s1*s2%mod;s2=s2*s2%mod;}
    return s1;
}
inline ll getinv(ll x,ll mod = MOD) {return power(x,mod - 2);};
ll fac[N],ifac[N];
void count_prepare(ll mod = MOD)
{
    fac[0]=1;for (int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
    ifac[N-1]=getinv(fac[N-1],mod);
    for (int i=N-2;i>=0;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
}
ll C(ll n,ll m,ll mod = MOD)
{
    if (n<0 || m<0 || m>n) return 0;
    return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
pii q[N];
int dis[N];
int n,m,st;
void init()
{
    scanf("%d%d%d",&n,&m,&st);
    for (int i=1;i<=m;++i) scanf("%d%d",&q[i].x,&q[i].y);
    for (int i=1;i<=n;++i) dis[i]=1e9;
    dis[st]=0;
    return;
}
void solve()
{
    for (int i=1;i<=m;++i)
    {
        int x=q[i].x,y=q[i].y;
        int p=min(dis[x]+1,dis[y]);
        int q=min(dis[y]+1,dis[x]);
        dis[x]=p;dis[y]=q;
        //for (int i=1;i<=n;++i) printf("%d%c",(dis[i]>m ? -1 : dis[i])," \n"[i==n]);
    }
    for (int i=1;i<=n;++i) printf("%d%c",(dis[i]>m ? -1 : dis[i])," \n"[i==n]);
    return;
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    for (int cas=1;cas<=T;++cas)
    {
        //printf("Case %d : \n",cas);
        init();
        solve();
    }
    return 0;
}