eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ядро рыцарей

Ядро рыцарей

Рыцарский средневековый конкурс заключается в том, что люди верхом на лошадях пытаются ударить друг друга деревянными копьями во время езды на высокой скорости. В общей сложности $2n$ рыцарей выступили в рыцарском турнире --- по $n$ рыцарей из каждого из двух больших конкурирующих домов. По прибытии на турнир каждый рыцарь вызвал одного рыцаря из другого дома на дуэль. Ядро определяется как некоторое подмножество $S$ рыцарей со следующими двумя свойствами: \begin{itemize} \item Ни один рыцарь из $S$ не был вызван на дуэль другим рыцарем из $S$. \item Каждый рыцарь не из $S$ был вызван на дуэль некоторым рыцарем из $S$. \end{itemize} По заданному множеству вызовов на дуэли найдите ядро. Гарантируется, что ядро всегда существует. \InputFile Первая строка содержит число $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)$. \OutputFile Вывести номера рыцарей в ядре в одной строке. Если существует более одного решения, вывести любое.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
4
5 6 7 7
1 3 2 3
Çıxış verilənləri #1
1 2 4 8 
Mənbə 2015 ACM Central Europe (CERC), Zagreb, November 13-15, Problem K