#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
typedef long long ll;
typedef pair<int,int>pii;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double pi = acos(-1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
const int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll poww(ll a, ll b) { ll s = 1; while (b) { if (b & 1)s = (s * a) % mod; a = (a * a) % mod; b >>= 1; }return s % mod; }
/*----------------------------------------------------------------------------------------------------------------------*/

const int N = 1e6 + 11;
ll n,m;
int z[N];
int q[N];
void solve()
{
    int l,r,a,b,k;
    cin>>n>>m>>k;
    rep(i,1,n)z[i]=-1;
    z[k]=0;
    rep(i,1,m)
    {
        cin>>l>>r;
        a=z[l];
        b=z[r];
        if(a!=-1&&b!=-1)z[r]=min(z[r]+1,a);
        else if(a!=-1)z[r]=a;
        else if(b!=-1)z[r]++;
        if(b!=-1&&a!=-1)z[l]=min(z[l]+1,b);
        else if(b!=-1)z[l]=b;
        else if(a!=-1)z[l]++;
    }
    rep(i,1,n-1)
        if(z[i]==-1)cout<<-1<<' ';
        else cout<<z[i]<<' ';
    if(z[n]==-1)cout<<-1<<endl;
    else cout<<z[n]<<endl;
}


/*----------------------------------------------------------------------------------------------------------------------*/
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll T = 1;
    cin >> T;
    while (T--)solve();
    return 0;
}