#define lli long long int
#define sf  scanf
#define pf  printf
#define pi                  acos(-1)
#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)
#define INF                 1000000000000000000
#define dist(ax,ay,bx,by)   sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
#define gcd(a,b)            __gcd(a,b)
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define m_p(a,b)            make_pair(a,b)
#define pb                  push_back
#define pii pair< int, int >
#define ppi pair< pii, int >
#define ff first
#define ss second
#define ms(name,reference)  memset(name,reference,sizeof(name))
#define fast                ios_base::sync_with_stdio(false),cin.tie(NULL)
#include<bits/stdc++.h>
using namespace std;
#define MAX 1005
vector<int>edge[MAX];
int level[MAX];
bool vis[MAX];
void bfs(int s)
{
	memset(vis,false,sizeof(vis));
	memset(level,-1,sizeof(level));
	queue<int>q;
	int u,v,i;
	level[s]=0;
	q.push(s);
	vis[s]=true;
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(i=0;i<edge[u].size();i++){
			v=edge[u][i];
			if(!vis[v]){
				vis[v]=true;
				level[v]=level[u]+6;
				q.push(v);
			}
		}
	}
}
int main()
{
	int t,m,n,a,b,i,x;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&m,&n);
		for(i=0;i<n;i++){
			scanf("%d %d",&a,&b);
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
		scanf("%d",&x);
		bfs(x);
		for(i=1;i<=m;i++){
			if(i==x)continue;
			printf("%d ",level[i]);
		}
        printf("\n");
		for(i=0;i<=m;i++)
			edge[i].clear();
	}
	return 0;
}