class graph
{
list*l;
ll int n;
public:
graph(ll int n)
{
this->n=n;
l=new list[n+1];
}
void add_edge(ll int v,ll int u)
{
l[v].push_back(u);
}
void short_path(int s)
{
ll int dist[n+1];
for(ll int i=1;i<=n;i++)
dist[i]=INT_MAX;
dist[s]=0;
queueq;
q.push(s);
while(!q.empty())
{
int node=q.front();
q.pop();
list<ll int>::iterator it;
for(it=l[node].begin();it!=l[node].end();++it)
{
if(dist[*it]==INT_MAX)
{
dist[*it]=dist[node]+1;
q.push(*it);
}
}
}
/*for(int i=1;i<=n;i++)
cout<<i<<"-->"<<dist[i]<<endl;*/
for(ll int i=1;i<=n;i++)
{
if(i!=s&&dist[i]!=INT_MAX)
cout<<dist[i]*6<<" ";
else if(i!=s&&dist[i]==INT_MAX)
cout<<"-1"<<" ";
}
}
};
int main()
{
ll int t;
cin>>t;
while(t–)
{
ll int n,m;
cin>>n>>m;
graph g(n);
while(m–)
{
ll int v,u;
cin>>v>>u;
g.add_edge(v,u);
}
ll int s;
cin>>s;
g.short_path(s);
cout<<endl;
}
return 0;
}
