3та

let [N, K] = gets().split(' ')
let students = gets().split(' ')
class LinkedListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.count = 0;

    }
    addLast(value) {
        const node = new LinkedListNode(value);
        if(!this.head) {
           this.head = node;
        } else {
           this.tail.next = node;
           node.prev = this.tail;
        }
        this.tail = node;

        this.count++;
      }

   insertBefore(node, value) {
        if (!this.head) {
            throw new Error('Empty list');
        }
        const newNode = new LinkedListNode(value);
        newNode.prev = node.prev;
        node.prev = newNode;
        newNode.next = node;
        if (newNode.prev !== null) {
          newNode.prev.next = newNode;
        } else {
         this.head = newNode;
        }
        this.count++;
    }

   find(val) {
        let ref = this.head;
        while(ref){
           if(ref.value === val) {
              return ref;
           }
           ref = ref.next;
        }
        return null;
      }

   moveBefore(val1, val2){
        let ref = this.head;
        let ref1 = null
        let ref2 = null
        while(ref){
            if(ref.value === val1){
                ref1 = ref
            }
            if(ref.value === val2){
                ref2 = ref
            }
            ref = ref.next;
        }
        this.removeNode(ref1);
        this.insertBefore(ref2,ref1.value);

      }

   removeNode(node){
        if(node === this.tail){
           this.tail.prev.next = null
           this.tail = this.tail.prev

        } else if(node === this.head) {
           this.head.next.prev = null;
           this.head = this.head.next;

        } else {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        }
        this.count--;
      }

   values() {
        let result = [];
        if(this.count===0){
           return result;
        }
        let ref = this.head.next.prev;// remembers the head in order not to modify the list;
        while(this.head){
           result.push(this.head.value);
           this.head = this.head.next;
        }
        this.head = ref;//resets the head reference
        return result;
      }
    }

const list = new DoublyLinkedList();
    for (let i = 0; i <= N; i++) {
        list.addLast(students[i]);
    }
const dict = new Map()
for (const stud of students) {
   dict.set(stud, list.find(stud))
}
for (let i = 1; i <= K; i++) {
        let [leftName, rightName] = gets().split(' ')

        let node1 = dict.get(leftName);

        list.removeNode(node1);
        dict.delete(leftName);
        //update the dict
        let node2 = dict.get(rightName);
        list.insertBefore(node2,leftName);
        if(node2 === list.head){
         dict.set(leftName,listHead)
        } else {
        dict.set(leftName,node2.prev)
        }
    }
console.log(list.values().join(' '));