package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

const INF = int32(1000000000)
const edgeWeight = int32(6)

/*
 * Complete the 'bfs' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER m
 *  3. 2D_INTEGER_ARRAY edges
 *  4. INTEGER s
 */

func bfs(n int32, m int32, edges [][]int32, s int32) []int32 {
    adjList := edgeListToAdjList(n, edges)
    
    dist := initDist(n)    
    dist[s] = 0
    
    var queue []int32
    queue = append(queue, s)
    
    for len(queue) != 0 {
        u := queue[0]
        queue = queue[1:]
        
        for _, v := range adjList[u] {
            if dist[v] == INF {
                dist[v] = dist[u] + 1
                queue = append(queue, v)
            }
        }
    }
    
    
    var result []int32
    
    for i := int32(1); i <= n; i++ {
        if i == s {
            continue
        }
        
        if dist[i] == INF {
            result = append(result, -1)
            
            continue
        }
        
        result = append(result, dist[i] * edgeWeight)
    }

    return result
}

func initDist(V int32) []int32 {
    dist := make([]int32, V+1)
    
    for i := int32(1); i <= V; i++ {
        dist[i] = INF
    }
    
    return dist
}

func edgeListToAdjList(V int32, edgeList [][]int32) [][]int32 {
    adjList := make([][]int32, V+1)
    
    for _, edge := range edgeList {
        u := edge[0]
        v := edge[1]
        
        adjList[u] = append(adjList[u], v)
        adjList[v] = append(adjList[v], u)
    }
    
    return adjList
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    qTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
    checkError(err)
    q := int32(qTemp)

    for qItr := 0; qItr < int(q); qItr++ {
        firstMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

        nTemp, err := strconv.ParseInt(firstMultipleInput[0], 10, 64)
        checkError(err)
        n := int32(nTemp)

        mTemp, err := strconv.ParseInt(firstMultipleInput[1], 10, 64)
        checkError(err)
        m := int32(mTemp)

        var edges [][]int32
        for i := 0; i < int(m); i++ {
            edgesRowTemp := strings.Split(strings.TrimRight(readLine(reader)," \t\r\n"), " ")

            var edgesRow []int32
            for _, edgesRowItem := range edgesRowTemp {
                edgesItemTemp, err := strconv.ParseInt(edgesRowItem, 10, 64)
                checkError(err)
                edgesItem := int32(edgesItemTemp)
                edgesRow = append(edgesRow, edgesItem)
            }

            if len(edgesRow) != 2 {
                panic("Bad input")
            }

            edges = append(edges, edgesRow)
        }

        sTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
        checkError(err)
        s := int32(sTemp)

        result := bfs(n, m, edges, s)

        for i, resultItem := range result {
            fmt.Fprintf(writer, "%d", resultItem)

            if i != len(result) - 1 {
                fmt.Fprintf(writer, " ")
            }
        }

        fmt.Fprintf(writer, "\n")
    }

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}