#include <bits/stdc++.h>
using namespace std;
int a[100050];
int x[100050],y[100050];
int main ()
{
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i = 1;i<=m;i++){
            scanf("%d%d",&x[i],&y[i]);
        }
        for(int i = 1;i<=n;i++){
            a[i] = -1;
        }
        
        a[k] = 0;
        
        for(int i = 1;i<=m;i++){
            int u1 = a[x[i]];
            int u2 = a[y[i]];
            if(u1==-1&&u2==-1)
            continue;
            else if(u2==-1){
                a[y[i]] = a[x[i]];
                a[x[i]]++;
            }
            else if(u1==-1){
                a[x[i]] = a[y[i]];
                a[y[i]]++;
                
            }
            else{
                a[x[i]] = min(u1+1,u2);
                a[y[i]] = min(u2+1,u1);
                
            }    
        }
        
        for(int i = 1;i<n;i++){
            printf("%d ",a[i]);        
        }
        cout<<a[n];
        cout<<endl;
    }
    
    
    return 0;
}