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);
const arr1 = gets().split(' ').map(Number);
const arr2 = gets().split(' ');
const n = arr1[0];
const k = arr1[1];
const testMap = new Map();
class LinkedListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
    }
    addLast(value) {
        const newNode = new LinkedListNode(value)
        if (!this.head)  {
            this.tail = newNode;
            this.head = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
    }
    insertBefore(node, nextNode) {
        if (!node.prev) {
            this.head = nextNode;
            nextNode.prev = null;
            nextNode.next = node;
            node.prev = nextNode;
        }
        else {
            nextNode.prev = node.prev;
            nextNode.next = node;
            node.prev = nextNode;
            nextNode.prev.next = nextNode;
        }
    }
    find(value) {
        let current = this.head;
        while (current !== null) {
            if (current.value === value) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    values() {
        const values = [];
        let current = this.head;
        while (current !== null) {
            values.push(current.value);
            current = current.next;
        }
        return values;
    }
    remove(node) {
        if (node.prev === null) {
            this.head = node.next;
            this.head.prev = null;
        } else if (node.next === null) {
            this.tail = node.prev;
            this.tail.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        return node
    }
}
const linkedList = new DoublyLinkedList();
for (let i = 0 ; i< arr2.length; i++) {
    linkedList.addLast(arr2[i])
    testMap.set(arr2[i], linkedList.find(arr2[i]));
}
for(let i = 0 ; i < k; i++){
    let currChange = gets().split(' ');
    let personToBeMoved = testMap.get(currChange[0]);
    let personToGoTo = testMap.get(currChange[1]);
    linkedList.remove(personToBeMoved);
    linkedList.insertBefore(personToGoTo, personToBeMoved);
}
print(linkedList.values().join(' '))