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