#include<bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PLI pair<LL,int>
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lowbit(x) (x&(-x))
using namespace std;

const int maxn=100010,inf=1e9+10;
int T,n,m,k,ans[maxn];

int main(){
#ifdef OJ
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            ans[i]=inf;
        }
        ans[k]=0;
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            if(ans[u]!=inf || ans[v]!=inf){
                if(ans[u]<ans[v]){
                    ans[v]=ans[u];
                    ans[u]=ans[v]+1;
                }
                else{
                    ans[u]=ans[v];
                    ans[v]=ans[u]+1;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(ans[i]==inf) ans[i]=-1;
        }
        for(int i=1;i<n;i++) printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
}