using System;

using System.Collections.Generic;

​

namespace GA

{

    class Program

    {

        static void Main(string[] args)

        {

            int n, m, r, i, u, v;

            n = int.Parse(Console.ReadLine());

            m = int.Parse(Console.ReadLine());

            r = int.Parse(Console.ReadLine());

            List<int>[] G = new List<int>[n + 1];

            List<int> T = new List<int>(n + 1); T.Add(0);

            for (i = 1; i <= n; i++)

            {

                G[i] = new List<int>(); T.Add(0);

                for (i = 1; i <= m; i++)

                {

                    u = int.Parse(Console.ReadLine());

                    v = int.Parse(Console.ReadLine());

                    G[u].Add(v); G[v].Add(u);

                }

                BFS(n, G, T, r);

                for (i = 1; i <= n; i++)

                {

                    Console.WriteLine("{0}: {1}", i, T[i]);

                }

            }

        }

​

        static void BFS(int n, List<int>[] G, List<int> T, int r)

        {

            int x, y, i;

            bool[] used = new bool[n + 1];

            Queue<int> Q = new Queue<int>();

            for (i = 1; i <= n; i++) used[i] = false;

            Q.Enqueue(r); used[r] = true; T[r] = 0;

            while(Q.Count>0)

            {

                x = Q.Dequeue();

                for(i = 0;i<G[x].Count;i++)

                {

                    y = G[x][i];

                    if (!used[y])

                    {

                        used[y] = true; T[y] = x; Q.Enqueue(y);

                    }

                    }

                }

            }

        }

    }