#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, k, dp[100005];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++) dp[i] = INF;
        dp[k] = 0;
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            swap(dp[x], dp[y]);
            dp[x] = min(dp[x], dp[y] + 1);
            dp[y] = min(dp[y], dp[x] + 1);
        }
        for (int i = 1; i <= n; i++) printf("%d%c", dp[i] == INF ? -1 : dp[i], " \n"[i == n]);
    }
    return 0;
}