using System using System Collections Generic using System Collections

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Arcs
{
    class ArcsBundle
    {
        protected readonly int Nmax;
        protected readonly int[] head;
        protected int[] dest;
        protected int[] next;
        protected int ArcsCap;
        public int ArcsCount { get; protected set; }
        private const int defaultCapacity = 50;

        public ArcsBundle(int Nmax)
        {
            this.Nmax = Nmax;
            head = new int[Nmax];
            for (int i = 0; i < Nmax; ++i)
            {
                head[i] = -1;
            }
            ArcsCount = 0;
            ArcsCap = defaultCapacity;
            dest = new int[ArcsCap];
            next = new int[ArcsCap];
        }

        public ArcsBundle(int Nmax, int capacity)
        {
            this.Nmax = Nmax;
            head = new int[Nmax];
            for (int i = 0; i < Nmax; ++i)
            {
                head[i] = -1;
            }
            ArcsCount = 0;
            ArcsCap = capacity;
            dest = new int[ArcsCap];
            next = new int[ArcsCap];
        }

        public ArcsBundle(int Nmax, int[] from, int[] to)
        {
            if (from.Length != to.Length)
            {
                throw new Exception("Wrong constructor args.");
            }
            this.Nmax = Nmax;
            head = new int[Nmax];
            for (int i = 0; i < Nmax; ++i)
            {
                head[i] = -1;
            }
            ArcsCount = 0;
            ArcsCap = from.Length;
            dest = new int[ArcsCap];
            next = new int[ArcsCap];
            for (int i = 0; i < ArcsCap; ++i)
            {
                AddArc(from[i], to[i]);
            }
        }

        public static ArcsBundle CreateUnorientedGraph(int vertnum, int[] u, int[] v)
        {
            if (u.Length != v.Length)
            {
                throw new Exception("Wrong constructor args.");
            }
            ArcsBundle ab = new ArcsBundle(vertnum, 2 * u.Length);
            for (int i = 0; i < u.Length; ++i)
            {
                ab.AddArc(v[i], u[i]);
                ab.AddArc(u[i], v[i]);
            }
            return ab;
        }

        public void AddArc(int from, int to)
        {
            if (ArcsCap == ArcsCount)
            {
                ArcsCap *= 2;
                int[] tDest = new int[ArcsCap];
                int[] tNext = new int[ArcsCap];
                dest.CopyTo(tDest, 0);
                next.CopyTo(tNext, 0);
                dest = tDest;
                next = tNext;
            }
            dest[ArcsCount] = to;
            next[ArcsCount] = head[from];
            head[from] = ArcsCount++;
        }

        public class Bundle : IEnumerable
        {
            protected ArcsBundle handler;
            public int vertex { get; protected set; }
            public Bundle(int v, ArcsBundle handler)
            {
                this.handler = handler;
                vertex = v;
            }

            public IEnumerator GetEnumerator()
            {
                for (int arc = handler.head[vertex]; arc != -1; arc = handler.next[arc])
                {
                    yield return handler.dest[arc];
                }
            }

        }

        public Bundle this[int vertex]
        {
            get
            {
                if (vertex < 0 || vertex >= Nmax)
                {
                    throw new Exception("Wrong vertex number");
                }
                return new Bundle(vertex, this);
            }
        }

        public void BfsFrom(int start, out int[] pred, out int[] dist)
        {
            Queue<int> q = new Queue<int>();
            pred = new int[Nmax];
            dist = new int[Nmax];
            for (int i = 0; i < Nmax; ++i)
            {
                dist[i] = int.MaxValue;
                pred[i] = -1;
            }
            dist[start] = 0;
            q.Enqueue(start);
            while(q.Count > 0)
            {
                int v = q.Dequeue();
                foreach (int u in this[v])
                {
                    if (u != start && pred[u] < 0)
                    {
                        pred[u] = v;
                        dist[u] = dist[v] + 1;
                        q.Enqueue(u);
                    }
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Func<string> getline;
            Action<string> putline;
            if (args.Length != 2){
                getline = (Func<string>)Console.ReadLine;
                putline = Console.WriteLine;
            }
            else
            {
                StreamReader sr = new StreamReader(args[0]);
                getline = sr.ReadLine;
                StreamWriter sw = new StreamWriter(args[1]);
                putline = sw.WriteLine;
            }
            string[] ts = getline().Split();
            int n, m, start;
            n = int.Parse(ts[0]);
            m = int.Parse(ts[1]);
            start = int.Parse(ts[2]);

            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < m; ++i)
            {
                ts = getline().Split();
                a[i] = int.Parse(ts[0]);
                b[i] = int.Parse(ts[1]);
            }

            ArcsBundle ab = ArcsBundle.CreateUnorientedGraph(n, a, b);

            int[] pred, dist;
            ab.BfsFrom(start, out pred, out dist);
            putline("digraph G {");
            string s = "";
            for (int i = 0; i < n; ++i)
                if (pred[i] >= 0)
                    s += i.ToString() + " ";
            putline(s);
            for (int x = 0; x < n; ++x)
                if (pred[x] >= 0)
                    putline(pred[x] + " -> " + x);
            putline("}");
        }
    }
}q