Ядро рыцарей
Ядро рыцарей
Рыцарский средневековый конкурс заключается в том, что люди верхом на лошадях пытаются ударить друг друга деревянными копьями во время езды на высокой скорости. В общей сложности 2n рыцарей выступили в рыцарском турнире — по n рыцарей из каждого из двух больших конкурирующих домов. По прибытии на турнир каждый рыцарь вызвал одного рыцаря из другого дома на дуэль.
Ядро определяется как некоторое подмножество S рыцарей со следующими двумя свойствами:
Ни один рыцарь из S не был вызван на дуэль другим рыцарем из S.
Каждый рыцарь не из S был вызван на дуэль некоторым рыцарем из S.
По заданному множеству вызовов на дуэли найдите ядро. Гарантируется, что ядро всегда существует.
Входные данные
Первая строка содержит число n~(1 \le n \le 10^5) — количество рыцарей из каждого дома. Рыцари из первого дома обозначаются числами от 1 до n, рыцари из другого дома — числами с n + 1 до 2n.
Следующая строка содержит целые числа f_1, f_2, ..., f_n — k-ое число f_k — номер рыцаря, вызванного на дуэль рыцарем k~(n + 1 \le f_k \le 2n).
Следующая строка содержит целые числа s_1, s_2, ..., s_n — k-ое число s_k — номер рыцаря, вызванного на дуэль рыцарем n + k~(1 \le s_k \le n).
Выходные данные
Вывести номера рыцарей в ядре в одной строке. Если существует более одного решения, вывести любое.
Пример
4 5 6 7 7 1 3 2 3
1 2 4 8