#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int n, m, k;
        cin >> n >> m >> k;
        const int inf = (int) 1e9;
        vector<int> a(n, inf);
        k--;
        a[k] = 0;
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--, y--;
            if (x == y) {
                continue;
            }
            int ax = a[x];
            int ay = a[y];
            a[x] = min(ax + 1, ay);
            a[y] = min(ax, ay + 1);
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == inf) {
                a[i] = -1;
            }
            if (i > 0) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << '\n';
    }
    return 0;
}