#include
#include<bits/stdc++.h>
#include
using namespace std;
long long int sum=0;
int count=0;
void insertedge(vectoradj[],long long int u,long long int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
void printedge(vectoradj[],long long int v){
for(int i=0;i<v;i++){
for(int j=0;j<adj[i].size();j++){
cout<<i<<" “<<adj[i][j]<<” “;
}
cout<<”\n";
}
}
void bfs(vectoradj[],int s,long long int v){
unordered_map<long long int,long long int>dist;
for(long long int i=0;i<v;i++){
dist[i]=INT_MAX;
}
long long int vis[v]={0};
dist[s]=0;
queueq;
q.push(s);
vis[s]=1;
while(!q.empty()){
long long int r=q.front();
q.pop();
for(auto j:adj[r]){
if(vis[adj[r][j]]){
if(dist[adj[r][j]]>dist[r]+6){
dist[adj[r][j]]=dist[r]+6;
}
else{
q.push(adj[r][j]);
dist[adj[r][j]]=dist[r]+6;
}
}
}
}
for(long long int i=0;i<v;i++) {
cout<<dist[i]<<" ";
}
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
vectoradj[a];
for(int j=0;j<b;j++){
long long int u,v;
cin>>u>>v;
insertedge(adj,u-1,v-1);
}
int s;
cin>>s;
bfs(adj,s-1,a);
cout<<"\n";
}
return 0;
}