import java.util.*;
public class Main {
static class Graph {
private class Vertex {// class with a hashmap to hold the neighbours of a vertex and the edge cost
HashMap<String, Integer> nbrs = new HashMap<>();
}
HashMap<String, Vertex> vtces;// hashmap to store the graph
public Graph() {
vtces = new HashMap<>();
}
public void addVertex(String vname) {
Vertex vtx = new Vertex();
this.vtces.put(vname, vtx);// empty vertex hashmap
}
public void addEdge(String vname1, String vname2, int cost) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if (vtx1 == null || vtx2 == null || vtx1.nbrs.containsKey(vname2)) {
return;
}
vtx1.nbrs.put(vname2, cost);
vtx2.nbrs.put(vname1, cost);
}
private class Pair {
String vname;
String psf;
}
public boolean containsEdge(String vname1, String vname2) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if (vtx1 == null || vtx2 == null || !vtx1.nbrs.containsKey(vname2)) {
return false;
}
return true;
}
public boolean bfs(String src, String dst) {
HashMap<String, Boolean> processed = new HashMap<>();
LinkedList<Pair> queue = new LinkedList<>();
// create a new pair
Pair sp = new Pair();
sp.vname = src;
sp.psf = src;
// put the new pair in queue
queue.addLast(sp);
// while queue is not empty keep on doing the work
while (!queue.isEmpty()) {
// remove a pair from queue
Pair rp = queue.removeFirst();
if (processed.containsKey(rp.vname)) {
continue;
}
// processed put
processed.put(rp.vname, true);
// check for direct edge
if (containsEdge(rp.vname, dst)) {
int ans = 0;
for(int i=0;i<rp.psf.length();i++) {
if(rp.psf.charAt(i)==' ') {
ans++;
}
}
System.out.print((ans+1)*6+" ");
return true;
}
// nbrs
Vertex rpvtx = vtces.get(rp.vname);
ArrayList<String> nbrs = new ArrayList<>(rpvtx.nbrs.keySet());
// loop on nbrs
for (String nbr : nbrs) {
// process only unprocessed nbrs
if (!processed.containsKey(nbr)) {
// make a new pair of nbr and put it in queue
Pair np = new Pair();
np.vname = nbr;
np.psf = rp.psf + " " + nbr;
queue.addLast(np);
}
}
}
return false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- != 0) {
int n = sc.nextInt();
int m = sc.nextInt();
Graph g = new Graph();
for (int i = 1; i <= n; i++) {
g.addVertex("" + i);
}
for (int i = 0; i < m; i++) {
g.addEdge("" + sc.nextInt(), "" + sc.nextInt(), 6);
}
int s = sc.nextInt();
for (int i = 1; i <=n; i++) {
if (i != s) {
if(!g.bfs("" + s,""+i)) {
System.out.print("-1 ");
}
}
}
}
}
}
