#include <bits/stdc++.h>

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    --k;
    std::vector<int> f(n, m + 1);
    f[k] = 0;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        int gu = std::min(f[u] + 1, f[v]);
        int gv = std::min(f[v] + 1, f[u]);
        f[u] = gu, f[v] = gv;
    }
    for (int i = 0; i < n; ++i) {
        if (f[i] == m + 1) {
            std::cout << -1;
        } else {
            std::cout << f[i];
        }
        std::cout << " \n"[i == n - 1];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
}