#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template< typename T > void read( T &x ) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while( !isdigit( ch ) ) {
        if( ch == '-' )
        f *= -1;
        ch = getchar();
    }
    while( isdigit( ch ) ) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64( uint64_t x ) {
        x += 0x9e3779b97f4a7c15;
        x = ( x ^ ( x >> 30 ) ) * 0xbf58476d1ce4e5b9;
        x = ( x ^ ( x >> 27 ) ) * 0x94d049bb133111eb;
        return x ^ ( x >> 31 );
    }

    size_t operator() ( uint64_t x ) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64( x + FIXED_RANDOM );
    }
};

int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 ), cout.tie( 0 );
    int t;
    cin >> t;
    while( t-- ) {
        int n, m, k;
        cin >> n >> m >> k;
        vector< int > a( n + 1, 1e9 );
        a[ k ] = 0;
        while( m-- ) {
            int x, y;
            cin >> x >> y;
            int tx = a[ x ], ty = a[ y ];
            a[ x ] = min( tx + 1, ty );
            a[ y ] = min( ty + 1, tx );
        }
        for( int i = 1; i <= n; ++i )
            cout << ( a[ i ] == 1e9? -1: a[ i ] ) << " \n"[ i == n ];
    }
    return 0;
}