#include
#include
#include
#include<limits.h>
#include
using namespace std;
template
class Graph
{ map <T, list > AdjList;
public:
Graph() {}
void addEdge(int u , int v , bool bidir = true) {
AdjList[u].push_back(v);
if ( bidir ) {
AdjList[v].push_back(u);
}
}
void bfs_shortest_path(T src , map <int , int>& dist ) {
queue q;
for (auto i : AdjList) { // iterator
dist[i.first] = INT_MAX;
}
q.push(src);
dist[src] = 0;
while (!q.empty()) {
T node = q.front(); q.pop();
for (auto neighbour : AdjList[node]) {
if (dist[neighbour] == INT_MAX) {
q.push(neighbour);
dist[neighbour] = dist[node] + 6;
}
}
}
}
void clear() {
AdjList.clear();
}
};
int main() {
int t; cin >> t;
for (int i = 0 ; i < t ; i++) {
Graph g;
int edges, nodes;
cin >> nodes >> edges;
for ( int i = 0 ; i < edges ; i++) {
int u, v;
cin >> u >> v;
g.addEdge(u, v);
}
int src;
cin >> src;
map<int , int> dist;
g.bfs_shortest_path(src , dist ) ;
for (int i = 1 ; i <= nodes ; i++ ) {
if (i != src)
if (dist.find(i) == dist.end()) {
cout << "-1 ";
}
else {
cout << dist[i] << " ";
}
}
cout << endl;
dist.clear();
g.clear();
}
}
