#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
 
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
 
using namespace std;
typedef long long ll;
 
#ifdef local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() {
    cout << endl;
}
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
    for (auto x: a)
        cout << x << ' ';
    err(args...);
}
template<typename T, typename... Args>
void err(T a, Args... args) {
    cout << a << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod=998244353;
const int N = 1e5+5;
const int M = N*100;
const int maxn=1e7+50;

ll ans[N];
ll b[N];
vector<pair<int,int> > edges;
int link[N];

void work() {
    int n, m, k;
    cin >> n >> m >> k;
    edges.clear();
    for (int i = 1; i <= n; ++i) {
        ans[i] = b[i] = inf;
        link[i] = 0;
    }
    b[k] = 0;
    ans[k] = m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        link[u]++;
        link[v]++;
        edges.emplace_back(u,v);
    }
    for (int i = 0; i < m; ++i) {
        auto &u = edges[i].first;
        auto &v = edges[i].second;
        --link[u];
        --link[v];
        ll tmpbu = b[u];
        b[u] = min(b[u] + 1, b[v]);
        ans[u] = min(ans[u], b[u] + link[u]);
        
        b[v] = min(b[v] + 1, tmpbu);
        ans[v] = min(ans[v], b[v] + link[v]);
    }
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        if (ans[i] >= inf) {
            cout << -1;
        }else {
            cout << ans[i];
        }
    }
    
    cout << "\n";
}
 
int main() {
#ifdef local
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // local
    IOS;
//    init();
     int t;
     cin>>t;
     while(t--)
        work();
    return 0;
}