let input = [
  "5 3",
  "Gosho Tosho Penka Miro Stanka",
  "Miro Gosho",
  "Gosho Stanka",
  "Stanka Miro",
];

let print = this.print || console.log;

let gets =
  this.gets ||
  (
    (arr, index) => () =>
      arr[index++]
  )(input, 0);

//LinkedListNode
class LinkedListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}
//DoublyLinkedList

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
    this.map = new Map();
  }

  moveBefore(value1, value2) {
    let valueToMove = this.find(value1); //miro
    let staticValue = this.find(value2); //gosho

    this.remove(valueToMove);
    this.insertBefore(staticValue, value1);
  }

  remove(node) {
    this.map.delete(node.value);

    let firstNodePrevious = node.prev; //penka
    let firstNodeNext = node.next; //stanka

    if (firstNodePrevious === null && firstNodeNext === null) {
      //do not handle
    } else if (firstNodePrevious === null) {
      firstNodeNext.prev = null;
      this.head = firstNodeNext;
    } else if (firstNodeNext === null) {
      firstNodePrevious.next = null;
      this.tail = firstNodePrevious;
    } else {
      firstNodePrevious.next = firstNodeNext; //penka.next = stanka
      firstNodeNext.prev = firstNodePrevious; //stanka.prev = penka
    }
  }

  addLast(value) {
    let node = new LinkedListNode(value);

    if (this.count === 0) {
      this.map.set(value, node);
      this.head = node;
      this.tail = node;
    } else {
      this.map.set(value, node);
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

  insertBefore(prevNode, value) {
    //insert an element with the given value before the given node
    let newNode = new LinkedListNode(value);
    this.count++;

    this.map.set(value, newNode);

    let tempPrevNode = prevNode;
    let previousNode = tempPrevNode.prev;

    if (previousNode !== null) {
      newNode.next = tempPrevNode;
      tempPrevNode.prev = newNode;
      previousNode.next = newNode;
      newNode.prev = previousNode;
    } else {
      newNode.next = tempPrevNode;
      tempPrevNode.prev = newNode;
      newNode.prev = null;
      this.head = newNode;
    }
  }

  find(value) {
    // returns the first node that has the given value or undefined if no such value exists
    if (this.map.has(value)) {
      let node = this.map.get(value);
      return node;
    } else {
      return null;
    }
  }

  values() {
    let values = [];
    let tempHead = this.head;

    while (tempHead !== null) {
      values.push(tempHead.value);
      tempHead = tempHead.next;
    }
    return values;
  }
}

//Solution

let firstLine = gets();
let [numberOfStudents, seat] = firstLine.split(" ");

let students = gets().split(" ");
//[Gosho Tosho Penka Miro Stanka]

let list = new DoublyLinkedList();

//add all students into the map
for (let index = 0; index < students.length; index++) {
  const student = students[index];
  list.addLast(student);
}

//move two of the students
for (let index = 0; index < seat; index++) {
  const seatChange = gets().split(" "); //Miro Gosho
  list.moveBefore(seatChange[0], seatChange[1]);
}

print(list.values().join(" "));
//print(list.values())