import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int queryCount = sc.nextInt();
        
        for(int i = 0; i < queryCount; ++i){
            int nodeCount = sc.nextInt();
            int edgeCount = sc.nextInt();
            HashMap<Integer, ArrayList<Integer>> edges = new HashMap<Integer, ArrayList<Integer>>();
            
            for(int j = 0; j < edgeCount; ++j){
                int from = sc.nextInt();
                int to = sc.nextInt();
                ArrayList<Integer> values = new ArrayList<Integer>();
                if(edges.containsKey(from)){
                    values = edges.get(from);
                    
                }
                
                values.add(to);
                edges.put(from, values);
                values = new ArrayList<Integer>();
                
                if(edges.containsKey(to)){
                    values = edges.get(to);
                    
                }
                
                values.add(from);
                edges.put(to, values);
                
            }
            
            int headNode = sc.nextInt();
            
            
            for(int j = 1; j <= nodeCount; ++j){
                Queue<Integer> queue = new LinkedList<Integer>();
                Boolean found = false;
                if(j != headNode){
                    queue.add(headNode);
                    HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
                    visited.put(headNode, true);
                    int dist = 0;
                    while(!queue.isEmpty() && !found){
                        int size = queue.size();
                        while(size > 0){
                            int temp = queue.poll();
                            if(temp == j){
                                found = true;
                                System.out.print(dist + " ");
                                break;
                            }
                            else{
                                if(edges.containsKey(temp)){
                                    ArrayList<Integer> relatives = edges.get(temp);
                                    
                                    for(int k = 0; k < relatives.size(); ++k){
                                        if(!visited.containsKey(relatives.get(k))){
                                            queue.add(relatives.get(k));
                                            visited.put(relatives.get(k), true);
                                        }
                                    }
                                    
                                }
                            }
                            --size;
                            
                        }
                        
                        dist += 6;
                        
                    }
                    
                    if(!found){
                        System.out.print(-1 + " ");
                    }
                    
                }
            }
            
            System.out.println();
            
        }
        
        sc.close();
        
        
    }
}