using System;//zad.1/124str

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

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

    { int x, y, i, k; 

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)

     { х = Q.Dequeue(); 

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

{ у = G[x][i]; 

if (!used[y]) 

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

}

     }

    }

​

        public 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}", і, T[i]); } 

​

    }

}