#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define LL long long
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define fi first
#define se second
#define maxn 200005
#define mod 9901
#define lowbit(x) x&-x

using namespace std;

const int inf=0x7fffffff;

int n,m,k,u[maxn],v[maxn];
int dp[maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        memset(dp,0x3f,sizeof(dp));
        int flag=dp[0];
        scanf("%d%d%d",&n,&m,&k);
        for (int i=1;i<=m;i++) scanf("%d%d",&u[i],&v[i]);
        dp[k]=0;
        for (int i=1;i<=m;i++)
        {
            int ui=dp[u[i]],vi=dp[v[i]];
            dp[v[i]]=min(dp[v[i]]+1,ui);
            dp[u[i]]=min(dp[u[i]]+1,vi);
        }
        for (int i=1;i<=n;i++)
        {
            printf("%d",dp[i]==flag?-1:dp[i]);
            if (i!=n) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}