#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define printYes puts("Yes")
#define printYES puts("YES")
#define printNo puts("No")
#define printNO puts("NO")

const ll inf=1000000000000000000; 
const ll mod=998244353;
const int N=100006;
int n,m,T,k;
int ans[N]; 
inline int read()
{
    int F=1,ANS=0;
    char C=getchar();
    while (C<'0'||C>'9')
    {
        if (C=='-') F=-1;
        C=getchar();
    }
    while (C>='0'&&C<='9')
    {
        ANS=ANS*10+C-'0';
        C=getchar();
    }
    return F*ANS;
}
inline char readchar()
{
    char C=getchar();
    while (C<33||C>126) C=getchar();
    return C;
}
inline int raed(){return read();}
void work()
{
    n=read(),m=read(),k=read();
    memset(ans,-1,sizeof(ans));
    ans[k]=0;
    for (int i=1;i<=m;i++) 
    {
        int x=read(),y=read();
        if (x==y) continue;
        if (ans[x]==-1&&ans[y]==-1) continue;
        if (ans[x]>-1&&ans[y]>-1)
        {
            int X=ans[x],Y=ans[y];
            ans[x]=min(X+1,Y);
            ans[y]=min(Y+1,X);
            continue;
        }
        if (ans[x]==-1) swap(x,y);
        ans[y]=ans[x];
        ans[x]++;
    }
    for (int i=1;i<=n;i++) 
    {
        printf("%d",ans[i]);
        if (i<n) printf(" ");
    }
    printf("\n");
    return;
}

int main()
{
    int tp=0;
    //0 : many test cases
    //1 : one test case
    if (tp==0) T=read();
    else T=1;
    while (T--)
    {
        work();
    }
    return 0;
}