#include <bits/stdc++.h>

const int maxn = 100111;

int n, m, k, a[maxn];
void solve()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=n; i++) a[i] = 0x3f3f3f3f;
    a[k] = 0;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int a1 = a[u], a2 = a[v];
        a[u] = std::min(a2, a1+1);
        a[v] = std::min(a1, a2+1);
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i] > m) a[i] = -1;
        printf("%d%c", a[i], i == n ?'\n':' ');
    }
}

int main()
{
    int tc;
    scanf("%d", &tc);
    while(tc--) solve();
    return 0;
}