#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int T;
int n, m, k;
int l[maxn + 10], r[maxn + 10], f[maxn + 10];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &l[i], &r[i]);
        }
        memset(f, 0x3f, sizeof f);
        f[k] = 0;
        for (int i = 1; i <= m; ++i) {
            int tl = f[l[i]], tr = f[r[i]];
            f[l[i]] = min(tl + 1, tr);
            f[r[i]] = min(tl, tr + 1);
        }
        for (int i = 1; i <= n; ++i)
            printf("%d%c", f[i] > m ? -1 : f[i], " \n"[i == n]);
    }
}