import java.io.*
import java.util.*
import java.util.Scanner.*

fun main(args: Array<String>) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT.
         */
    val query = readln().toInt()
    
    for(i in 0 until query){
        val c = HashMap<Int, HashSet<Int>>()    
        val q: Queue<Int> = LinkedList()
        val nm = readln().split(" ")
        val n = nm[0].toInt()
        val m = nm[1].toInt()
        
        for(i in 0 until m){
            val uv =  readln().split(" ")
            val u = uv[0].toInt()
            val v = uv[1].toInt()
            if(c[u] == null){
                c[u] = HashSet()
            }  
            if(c[v] == null){
                c[v] = HashSet()
            }
            c[u]!!.add(v) 
            c[v]!!.add(u) 
        }
        
        val s = readln().trim().toInt()
        
        val visited = Array(n){0}
        
        q.offer(s)
        
        while(q.isNotEmpty()){
            val node = q.peek()
            c[node]?.forEach{
                if (visited[it - 1] == 0) {
                    visited[it - 1] = visited[node - 1] + 6
                    q.offer(it) 
                } 
            }
            q.poll()  
        }
        
        val sb = StringBuilder()
        for (i in visited.indices){
            val v = visited[i]
            if(i +1 != s ) {
                if (v > 0){
                    sb.append(v)
                } else {
                    sb.append("-1")
                }
                if(i != visited.lastIndex) {
                    sb.append(" ") 
                } 
            } 
        } 
        
        println(sb.toString())
    }
}