import java.util.;
import java.io.;
class Graph {
HashMap<Integer, Set<Integer>> adj;
Graph(int n) {
adj = new HashMap<>();
for (int i = 1; i <= n; i++) {
addEdge(i);
}
}
void addEdge(int a){
if(!adj.containsKey(a)){
adj.put(a,new HashSet<Integer>());
}
}
void addEdge(int a, int b) {
if (adj.containsKey(a)) {
Set<Integer> s = adj.get(a);
s.add(b);
adj.put(a, s);
} else {
Set<Integer> s = new HashSet<>();
s.add(b);
adj.put(a, s);
}
if (adj.containsKey(b)) {
Set<Integer> s = adj.get(b);
s.add(a);
adj.put(b, s);
} else {
Set<Integer> s = new HashSet<>();
s.add(a);
adj.put(b, s);
}
}
public String toString(){
return adj.toString();
}
}
class Main {
static int M = (int)(1e9 + 7);
static File f = null;
static Scanner sc = null;
static PrintWriter pw = null;
public static void main(String[] args)throws IOException {
try {
// f = new File(“input.txt”);
// sc = new Scanner(f);
// pw = new PrintWriter(new BufferedWriter(new FileWriter(“output.txt”)));
sc=new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
while (t-- > 0) {
testCase();
}
// pw.flush();
} catch (Exception e) {
// pw.flush();
e.printStackTrace();
}
}
static void SSSP(Graph g, int src) {
HashMap<Integer, Integer> dist = new HashMap<>();
Queue<Integer> q = new LinkedList<>();
int d = 1;
for (Integer s : g.adj.keySet())
dist.put(s, Integer.MAX_VALUE);
dist.put(src, 0);
q.add(src);
Set<Integer> visited = new HashSet<>();
while (q.size() > 0) {
Integer curr = q.poll();
visited.add(curr);
for (Integer dest : g.adj.get(curr)) {
if (!visited.contains(dest)){
dist.put(dest, dist.get(curr) + 6);
q.add(dest);
}
}
}
for (Integer s : dist.keySet()) {
if (s==src)
continue;
if (dist.get(s) == Integer.MAX_VALUE) dist.put(s, -1);
// pw.print(s+"= "+dist.get(s) + " "+"\n");
System.out.print(dist.get(s)+" ");
}
System.out.println();
}
static void testCase() {
int n = sc.nextInt();
int e = sc.nextInt();
sc.nextLine();
Graph g = new Graph(n);
for (int i = 0; i < e; i++) {
String arr[] = sc.nextLine().split(" ");
g.addEdge(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]));
}
int src = sc.nextInt();
// pw.println("Graph="+g);
SSSP(g, src);
}
}
