eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ядро рыцарей

Ядро рыцарей

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Рыцарский средневековый конкурс заключается в том, что люди верхом на лошадях пытаются ударить друг друга деревянными копьями во время езды на высокой скорости. В общей сложности 2n рыцарей выступили в рыцарском турнире — по n рыцарей из каждого из двух больших конкурирующих домов. По прибытии на турнир каждый рыцарь вызвал одного рыцаря из другого дома на дуэль.

Ядро определяется как некоторое подмножество S рыцарей со следующими двумя свойствами:

  • Ни один рыцарь из S не был вызван на дуэль другим рыцарем из S.

  • Каждый рыцарь не из S был вызван на дуэль некоторым рыцарем из S.

По заданному множеству вызовов на дуэли найдите ядро. Гарантируется, что ядро всегда существует.

Входные данные

Первая строка содержит число n~(1 \le n \le 10^5) — количество рыцарей из каждого дома. Рыцари из первого дома обозначаются числами от 1 до n, рыцари из другого дома — числами с n + 1 до 2n.

Следующая строка содержит целые числа f_1, f_2, ..., f_nk-ое число f_k — номер рыцаря, вызванного на дуэль рыцарем k~(n + 1 \le f_k \le 2n).

Следующая строка содержит целые числа s_1, s_2, ..., s_nk-ое число s_k — номер рыцаря, вызванного на дуэль рыцарем n + k~(1 \le s_k \le n).

Выходные данные

Вывести номера рыцарей в ядре в одной строке. Если существует более одного решения, вывести любое.

Пример

Входные данные #1
4
5 6 7 7
1 3 2 3
Выходные данные #1
1 2 4 8 
Источник 2015 ACM Central Europe (CERC), Zagreb, November 13-15, Problem K