#include <iostream>
using namespace std;
int dp[100005];
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        int n,m,k;
        cin >> n >> m >> k;
        for(int i=1;i<=n;i++) dp[i]=1e9;
        dp[k]=0;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin >> x >> y;
            int X=dp[x],Y=dp[y];
            dp[x]=min(X+1,Y);
            dp[y]=min(Y+1,X);
        }
        if(dp[1]>n+1000000) dp[1]=-1;
        cout << dp[1];
        for(int i=2;i<=n;i++)
        {
            if(dp[i]>n+1000000) dp[i]=-1;
            cout << " " << dp[i];
        }
        cout << "\n";
    }
    return 0;
}