1

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

namespace _3zadacha
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph g;
            List<string> names;
            using (var sr = new StreamReader("input.txt"))
            {
                List<List<int>> tunnels = new List<List<int>>();
                string exit = sr.ReadLine();
                string str1 = sr.ReadToEnd();
                int n = countPeregorodok(str1);
                names = str1.Split(new char[] { ' ', '-', '#' }, StringSplitOptions.RemoveEmptyEntries).ToList();
                for (int i = 0; i < n; i++)
                {
                    tunnels.Add(new List<int>());
                }


                int countBunkers, countExits  = 1, countTunnels = n;
                List<int> exits = new List<int>();

                for (int i = 0; i < countTunnels; i++)
                {
                    tunnels.Add(new List<int>());
                }
                sr.
                string[] str;
                for (int i = 0; i < countTunnels; i++)
                {
                    str = sr.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                    tunnels[int.Parse(str[0]) - 1].Add(int.Parse(str[1]) - 1);
                    tunnels[int.Parse(str[1]) - 1].Add(int.Parse(str[0]) - 1);
                }

                g = new Graph(names.Count, countTunnels, exits, tunnels);
            }

            int[] minDistance = SearchPath(g);
            using (var sw = new StreamWriter("output.txt"))
            {
                foreach (int dist in minDistance)
                {
                    sw.Write(names[dist] + " ");
                }
            }
        }
        public static int countPeregorodok(string str)
        {
            int count = 0;
            Regex reg = new Regex(@"[-]");
            count = reg.Matches(str).Count;
            return count;
        }
        public static int[] SearchPath(Graph g)
        {
            int[] minDistToPoint = new int[g.countPoints];
            for (int i = 0; i < g.countPoints; i++)
            {
                minDistToPoint[i] = -1;
            }

            Queue<int> pathToPoint = new Queue<int>();
            for (int j = 0; j < g.specificPoints.Count; j++)
            {
                pathToPoint.Enqueue(g.specificPoints[j]);
                minDistToPoint[g.specificPoints[j]] = 0;
            }

            while (pathToPoint.Count != 0)
            {
                int currentPoint = pathToPoint.Peek();
                pathToPoint.Dequeue();

                for (int k = 0; k < g.listPoints[currentPoint].Count; k++)
                {
                    if (minDistToPoint[g.listPoints[currentPoint][k]] == -1)
                    {
                        pathToPoint.Enqueue(g.listPoints[currentPoint][k]);
                        minDistToPoint[g.listPoints[currentPoint][k]] = minDistToPoint[currentPoint] + 1;
                    }
                }
            }
            return minDistToPoint;
        }
    }
    public class Graph
    {
        private int __countPoints;
        public int countPoints
        {
            get { return __countPoints; }
            set
            {
                if (value < 1)
                {
                    throw new ArgumentException("Неверный ввод данных");
                }
                else __countPoints = value;
            }
        }
        private int __countEdges;
        public int countEdges
        {
            get { return __countEdges; }
            set
            {
                if (value < 0)
                {
                    throw new ArgumentException("Неверный ввод данных");
                }
                else __countEdges = value;
            }
        }
        public List<List<int>> listPoints = new List<List<int>>();
        public List<int> specificPoints = new List<int>();
        public Graph(int countPoints, int countEdges, List<int> specificPoints, List<List<int>> listPoints)
        {
            this.countPoints = countPoints;
            this.countEdges = countEdges;
            this.specificPoints = specificPoints;
            this.listPoints = listPoints;
        }
    }
}