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

int n, m, K;
int f[101111];
void work() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i++) {
        f[i] = i == K ? 0 : 0x3f3f3f3f;
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        int nxtx = f[y], nxty = f[x];
        f[x] = min(f[x] + 1, nxtx);
        f[y] = min(f[y] + 1, nxty);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", f[i] > m ? -1 : f[i], i == n ? '\n' : ' ');
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) work();
}