#include <cassert>
#include <iostream>
#include <functional>
#include <iomanip>
#include <set>
#include <numeric>
#include <unordered_map>
#include <map>
#include <queue>
#include <stack>
#include <complex>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath> 
#include <random>
#include <vector>

using namespace std;

using LL = long long;

const LL base = 1000000007;
const int MAX = 100000 + 100;
void solve() {
    int n,m, kp;
    cin >>n>>m>>kp;
    int z[MAX] = {0};
    memset(z, 1, sizeof(z));
    z[kp] = 0;
    for (int i=0; i<m; ++i) {
        int a,b;
        cin >>a>>b;
        int x1 = min(z[a] + 1, z[b] );
        int x2 = min(z[a]  , z[b] + 1);
        z[a] = x1;
        z[b] = x2;
    }
    for (int i=1; i<=n; ++i) {
        int r =  z[i];
        if (r>m) r = -1;
        if (i<n) cout<<r<<' ';
        else cout<<r;
    }
    cout<<endl;
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //int a = getct(gap + 123);
    //int b = getct2(gap+123);
    int T;
    cin >>T;
    for (int tp=0; tp<T; ++tp) {
        solve();
    }

}