using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    public class Graph
    {
        private readonly Dictionary<int, Node> _nodeLookup = 
        new Dictionary<int, Node>();
        public int Size { get; set; }

        public class Node
        {
            private int _id;
            public int DistanceToSource { get; set; }

            public Node(int id)
            {
                _id = id;
                DistanceToSource = -1;
            }
            public List<Node> Adjacent = new List<Node>();
        }

        public Graph(int size)
        {
            Size = size;
            for (var i = 1; i <= size; i++)
                AddNode(i);
        }

        public Node GetNode(int id)
        {
            return _nodeLookup[id];
        }

        private void AddNode(int nodeId)
        {
            var n = new Node(nodeId);
            _nodeLookup.Add(nodeId, n);
        }

        public void AddEdge(int first, int second)
        {
            var source = GetNode(first);
            var destination = GetNode(second); 
            // Bidirectional Graph needs both edges
            source.Adjacent.Add(destination);      
            destination.Adjacent.Add(source);      
        }

        public int[] ShortestReach(int startId)
        { 
            var nextToVisit = new Queue<Node>();
            var startNode = GetNode(startId);
            startNode.DistanceToSource = 0;
            nextToVisit.Enqueue(startNode);
            while (nextToVisit.Any())
            {
                var node = nextToVisit.Dequeue();
                foreach (var adj in node.Adjacent)
                {
                    if (adj.DistanceToSource > -1 &&
                        adj.DistanceToSource <= 
                        node.DistanceToSource + 1) continue;     
                    adj.DistanceToSource =
                    	node.DistanceToSource + 1;
                    nextToVisit.Enqueue(adj);
                }
            }

            var shortestReach = _nodeLookup
                .Where(i => i.Key != startId)
                .OrderBy( i => i.Key)
                .Select(i => i.Value.DistanceToSource)
                .ToArray();

            return shortestReach;
        }
    }
    public static void Main(string[] args)
    {
        var q = Convert.ToInt32(Console.ReadLine());
        for (var i = 0; i < q; i++)
        {
            var temp = Console.ReadLine().Split(' ')
                              .Select( int.Parse )
                              .ToArray();
            var n = temp[0];
            var m = temp[1];
            var graph = new Graph(n);
            for (var j = 0; j < m; j++)
            {
                temp = Console.ReadLine().Split(' ')
                              .Select( int.Parse )
                              .ToArray();
                graph.AddEdge(temp[0], temp[1]);
            }
            var startId = Convert.ToInt32(Console.ReadLine());
            var shortestReach = graph.ShortestReach(startId);
            foreach (var dist in shortestReach)
            {
                Console.Write(dist != -1 ? dist * 6 : dist);
                Console.Write(' ');
            }
            Console.WriteLine();
        }
    }
}