#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
template <typename T>
void read(T &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; !isdigit(c); c = getchar())
        f |= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ '0');
    if (f) x = -x;
}

template <typename T>
void write(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x;
    static short st[30], tp;
    do st[++tp] = x % 10, x /= 10; while (x);
    while (tp) putchar(st[tp--] | '0');
    putchar(ed);
}

const int N = 100050;
int n, m, k, T, las[N];
int main() {
    for (read(T); T; T--) {
        read(n), read(m), read(k);
        memset(las, 0x3f, sizeof(las)), las[k] = 0;
        for (int i = 1, x, y;i <= m; ++i) {
            read(x), read(y);
            int a = las[x], b = las[y];
            las[x] = min(b, a + 1), las[y] = min(a, b + 1);
        }
        for (int i = 1;i <= n; ++i)
            write(las[i] > m ? -1 : las[i], " \n"[i == n]);
    }
    return 0;
}