Untitled

class ListNode {
  constructor(value, next = null, prev = null) {
    this.value = value;
    this.next = next;
    this.prev = prev;
  }
}

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

  get mapped() {
    const result = new Map();
    let tempNode = this.head;

    while (tempNode) {
      result.set(tempNode.value, tempNode);
      tempNode = tempNode.next;
    }

    return result;
  }

  get values() {
    const result = [];
    let node = this.head;

    while (node) {
      result.push(node.value);
      node = node.next;
    }

    return result.join(' ');
  }

  addNode(value) {
    const node = new ListNode(value);

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

    this.count++;
  }

  insert(leftNode, rightNode) {
    leftNode.prev = null;
    leftNode.next = null;

    if (rightNode === this.head) {
      this.head = leftNode;
    } else {
      leftNode.prev = rightNode.prev;
      rightNode.prev.next = leftNode;
    }

    leftNode.next = rightNode;
    rightNode.prev = leftNode;
  }

  remove(node) {
    if (node === this.tail && node === this.head) {
      this.head = null;
      this.tail = null;
    } else if (node === this.head) {
      this.head = this.head.next;
      this.head.prev = null;
    } else if (node === this.tail) {
      this.tail = this.tail.prev;
      this.tail.next = null;
    } else {
      const prevNode = node.prev;
      const nextNode = node.next;
      node.prev = null;
      node.next = null;

      if (prevNode) {
        prevNode.next = nextNode;
      }

      if (nextNode) {
        nextNode.prev = prevNode;
      }
    }
  }
}

const [n, k] = gets().split(' ').map(Number);

const names = gets().split(' ');
const linkedList = new LinkedList();

for (let i = 0; i < n; i++) {
  linkedList.addNode(names[i]);
}

const studentMap = linkedList.mapped;

for (let i = 0; i < k; i++) {
  const [left, right] = gets().split(' ');

  const nodeLeft = studentMap.get(left);
  const nodeRight = studentMap.get(right);
  linkedList.remove(nodeLeft);
  linkedList.insert(nodeLeft, nodeRight);
}

print(linkedList.values);