students order

public class StudentsOrder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int K = Integer.parseInt(scanner.nextLine().split(" ")[1]);
        Map<String, Node> seats = new HashMap<>();
        MyStudentsList studentsList = new MyStudentsList();
        for (String student : scanner.nextLine().split(" ")) {
            Node node = studentsList.addLast(student);
            seats.put(student, node);
        }
        for (int i = 0; i < K; i++) {
            String[] seatsChange = scanner.nextLine().split(" ");
            String stud1 = seatsChange[0];
            String stud2 = seatsChange[1];

            Node currentSeat = seats.get(stud1);
            Node targetSeat = seats.get(stud2);
            studentsList.addBefore(currentSeat, targetSeat);
        }

        for (String s : studentsList) {
            System.out.print(s + " ");
        }
    }
}
class Node {
    final String value;
    Node prev;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class MyStudentsList implements Iterable<String> {
    private Node head;
    private Node tail;
    private int size = 0;

    public MyStudentsList(){

    }

    public Node addLast(String name) {
        Node newNode = new Node(name);
        if(size == 0){
            head = tail = newNode;
        } else{
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return tail;
    }

    public void addBefore(Node currentSeat, Node targetSeat) {
        if (currentSeat.next == targetSeat){
            return;
        } else if (currentSeat == head){
            removeFirst();
        } else if (currentSeat == tail){
            removeLast();
        } else {
            currentSeat.prev.next = currentSeat.next;
            currentSeat.next.prev = currentSeat.prev;
        }

        if (targetSeat == head){
            insertFirst(currentSeat);
            return;
        }

        targetSeat.prev.next = currentSeat;
        currentSeat.prev = targetSeat.prev;

        currentSeat.next = targetSeat;
        targetSeat.prev = currentSeat;
    }

    private void insertFirst(Node node) {
        node.next = head;
        head.prev = node;
        head = node;
    }

    private void removeFirst(){
        head = head.next;
        head.prev = null;
    }

    private void removeLast(){
        tail = tail.prev;
        tail.next = null;
    }

    public int size() {
        return size;
    }

    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            Node current = head;
            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public String next() {
                String value = current.value;
                current = current.next;
                return value;
            }
        };
    }
}