#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e5 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, k;

int dp[maxn];

int main(){
    //freopen("in.txt", "r", stdin);
    int T; cin >> T;
    while(T--){
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++) dp[i] = INF;
        dp[k] = 0;
        while(m--){
            int u, v; scanf("%d %d",&u,&v);
            int du = min(dp[u] + 1, dp[v]);
            int dv = min(dp[v] + 1, dp[u]);
            dp[u] = du; dp[v] = dv;
        }
        for(int i=1;i<=n;i++) printf("%d%c",dp[i]==INF ? -1 : dp[i],i==n ? '\n' : ' ');
    }
    return 0;
}