#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 100;

int n, m, k;
int sa[N], dp[N];

int main() {
    //freopen("0.txt", "r", stdin);
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        dp[k] = 0;
        for (int i = 1; i <= m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            int x = dp[a], y = dp[b];
            dp[a] = min(y, x + 1);
            dp[b] = min(x, y + 1);
        }
        for (int i = 1; i <= n; i++) {
            if (dp[i] > 1e9) printf("%d", -1);
            else printf("%d", dp[i]);
            if (i == n) puts("");
            else putchar(' ');
        }
    }
    return 0;
}