#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 998244353;
const int maxn = 100100;

int f[maxn];

int main(void) {
    //freopen("c.in", "r", stdin);
    int T; scanf("%d", &T);
    while (T--) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);

        for (int i=1; i<=n; i++) f[i] = m + 1;
        f[k] = 0;
        for (int i=0; i<m; i++) {
            int u, v; scanf("%d%d", &u, &v);
            int pu = f[u], pv = f[v];
            f[u] = min(pu + 1, pv);
            f[v] = min(pv + 1, pu);
        }

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

    }
    return 0;
}
// dp[i, j] := i steps, min -> j
// (u, v) : dp[i, j] = dp[i-1, j]
// dp[i, u] = min(dp[i-1, u] + 1, dp[i-1, v])
// dp[i, v] = min(dp[i-1, v] + 1, dp[i-1, u])