#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
int f[maxn];

template <typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

void solve()
{
    int n, m, k, x, y;
    read(n); read(m); read(k);
    memset(f, 0x3f, sizeof(f));
    f[k] = 0;

    for (int i = 1; i <= m; i++)
    {
        read(x); read(y);
        int fx = f[x], fy = f[y];
        f[y] = min(f[y] + 1, fx);
        f[x] = min(f[x] + 1, fy);
    }

    for (int i = 1; i < n; i++)
        printf("%d ", f[i] > m ? -1 : f[i]);
    printf("%d\n", f[n] > m ? -1 : f[n]);
}

int main()
{
    int T;
    read(T);
    while (T--)
        solve();
}