#include<bits/stdc++.h>                   // below comment for pbds
#include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
#include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); // number of 
#define ll long long                      //element strictly smaller than it;
#define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort  use as s.f();
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std; // assert(a[i]<n ) // if we want to check for special cond , used for debug                     
using namespace __gnu_pbds; // make less_equal in order to make a multiset pbds
#define INF (ll)1e18 
const ll Mod = (ll)1e9+7;
ll CaseN=1;
const ld PI = 22/7.0;

ll tst()
{
ll ans=0;

return ans;
}

vector<vector<ll>> g(1002);
vector<bool> vis(1002,false);
ll n,m;
vector<ll> d(1002,LLONG_MAX);
queue<ll> q;
ll s;
//ll dis=0;

void bfs(ll src)
{
	
	while(!q.empty())
	{
	//dis++;
	ll p = q.front();
	//cout<<p<<"+";
	vis[p]=true;
	q.pop();
	for(auto x: g[p])
	{
	if(vis[x]==false)
	{
		q.push(x);	
		d[x]= min(d[x],d[p]+1);
		//d[x]=min(d[x],dis);
	}
	}
		
	}
	
return;	
}

void solve()
{		
	cin>>n>>m;
	//q.clear();
	for(ll i=1;i<=n;i++)
	{
		vis[i]=false;
		g[i].clear();
		d[i]=LLONG_MAX;
	}	
	
	for(ll i=0;i<m;i++)
	{
	ll u,v;
	cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);		
	}

	cin>>s;
	q.push(s);
	d[s]=0;
	
	//cout<<"::"<<d[3]<<endl;
	
	bfs(s);
	
	//cout<<endl;
	for(ll i=1;i<=n;i++)
	{
	if(i==s)
	{
	continue;	
	}	
	if(d[i]==LLONG_MAX)
	cout<<"-1"<<" ";	
	else
	cout<<d[i]*6<<" ";	
	}
	cout<<endl;
	
		//cout<<"Case #"<<CaseN<<": ";
		CaseN++;
		// print your ans below;
	
return ;

}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t=1;
	cin>>t;
	while(t--)
	{
	solve();
	}
	
}