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

namespace ShortestPathDemo
{
    class Vertex
    {
        public int Id { get; set; }
        public List<Vertex> Adj { get; set; }
        public Vertex Parent { get; set; }
        public bool Discovered { get; set; }

        public Vertex(int id)
        {
            this.Id = id;
            this.Adj = new List<Vertex>();
            Discovered = false;
            Parent = null;
        }

        public override string ToString()
        {
            string ps = Parent == null ? "-" : Parent.Id.ToString();
            string ds = Discovered ? "D" : "U";
            string s = string.Format("{0}:{1} P:{2}::", this.Id, ds, ps);
            foreach(Vertex nb in Adj)
            {
                s += string.Format(" {0}", nb.Id);
            }
            return s;
        }
    }
}





#define LOCAL
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ShortestPathDemo
{
    class Program
    {
        static void Main(string[] args)
        {
#if LOCAL
            TextReader stdin = Console.In;
            Console.SetIn(new StreamReader("graph.txt"));
#endif
            int nV = int.Parse(Console.ReadLine());
            List<Vertex> vertices = new List<Vertex>();
            for(int v = 0; v < nV; v++)
            {
                vertices.Add(new Vertex(v));
            }

            string line = Console.ReadLine();
            string[] parts = line.Split(' ');
            int nStart = int.Parse(parts[0]);
            int nFin = int.Parse(parts[1]);

            line = Console.ReadLine();
            while (line != null)
            {
                parts = line.Split(' ');
                int n1 = int.Parse(parts[0]);
                int n2 = int.Parse(parts[1]);
                Vertex v1 = vertices[n1];
                Vertex v2 = vertices[n2];
                v1.Adj.Add(v2);
                line = Console.ReadLine();
            }
            Vertex start = vertices[nStart];
            start.Discovered = true;
            Queue<Vertex> q = new Queue<Vertex>();
            q.Enqueue(start);
            while (q.Count > 0)//while Vertices in Queue
            {
                Vertex vtx = q.Dequeue();
                foreach(Vertex nb in vtx.Adj)
                {
                    if (!nb.Discovered)
                    {
                        nb.Discovered = true;
                        nb.Parent = vtx;
                        q.Enqueue(nb);
                    }
                }
            }
            foreach (Vertex vtx in vertices) Console.WriteLine(vtx);
            Vertex tmp = vertices[nFin];
            Stack<int> stk = new Stack<int>();
            while (tmp.Parent != null)
            {
                stk.Push(tmp.Id);
                tmp = tmp.Parent;
            }
            Console.Write(nStart);
            while (stk.Count > 0) Console.Write(" " + stk.Pop());
            Console.WriteLine();

#if LOCAL
            Console.SetIn(stdin);
            Console.ReadLine();
#endif
        }
    }
}