using System;

public 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++)

      { 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]); }

   }

}