#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;

const int N=200200,oo=1e9;

int T,n,m,k;
int x,y;
int ans[N];

int main()
{
    
    cin>>T;
    while(T--)
    {
    
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    ans[i]=oo;
    ans[k]=0;
    
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int A=ans[x],B=ans[y];
        ans[x]=min(A+1,B);
        ans[y]=min(A,B+1);
    }
    
    for(int i=1;i<=n;i++)
    {
        if(ans[i]<oo)
        printf("%d",ans[i]);
        else
        printf("-1");
        if(i<n)
        printf(" ");
    }
    //if(T!=0)
    cout<<"\n";
}
    
    
    return 0;
}