StudentsOrder

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

namespace StudentsOrder
{
    class Program
    {

        static void Main(string[] args)
        {
            var input = int.Parse(Console.ReadLine().Split()[1]);

            ICollection<string> orderSt = Console.ReadLine().Split();
            LinkedList<string> finalOrder = new LinkedList<string>();
            Dictionary<string, LinkedListNode<string>> dic = new Dictionary<string, LinkedListNode<string>>();
            foreach (var item in orderSt)
            {
                var node = finalOrder.AddLast(item);
                dic.Add(item, node);
            }

            for (int i = 0; i < input; i++)
            {
                var change = Console.ReadLine().Split();

                finalOrder.Remove(dic[change[0]]);
                finalOrder.AddBefore(dic[change[1]], dic[change[0]]);
            }

            Console.WriteLine(String.Join(" ", finalOrder));
        }
    }
}