eolymp
bolt
Try our new interface for solving problems
Problems

Kernel Knights

Kernel Knights

Jousting is a medieval contest that involves people on horseback trying to strike each other with wooden lances while riding at high speed. A total of $2n$ knights have entered a jousting tournament --- $n$ knights from each of the two great rival houses. Upon arrival, each knight has challenged a single knight from the other house to a duel. A kernel is defined as some subset $S$ of knights with the following two properties: \begin{itemize} \item No knight in $S$ was challenged by another knight in $S$. \item Every knight not in $S$ was challenged by some knight in $S$. \end{itemize} Given the set of the challenges issued, find one kernel. It is guaranteed that a kernel always exists. \InputFile The first line contains an integer $n~(1 \le n \le 10^5)$ --- the number of knights of each house. The knights from the first house are denoted with integers $1$ through $n$, knights from the second house with integers $n + 1$ through $2n$. The following line contains integers $f_1, f_2, ..., f_n$ --- the $k$-th integer $f_k$ is the index of the knight challenged by knight $k~(n + 1 \le f_k \le 2n)$. The following line contains integers $s_1, s_2, ..., s_n$ --- the $k$-th integer $s_k$ is the index of the knight challenged by knight $n + k~(1 \le s_k \le n)$. \OutputFile Output the indices of the knights in the kernel on a single line. If there is more than one solution, you may output any one.
Time limit 1 second
Memory limit 256 MiB
Input example #1
4
5 6 7 7
1 3 2 3
Output example #1
1 2 4 8 
Source 2015 ACM Central Europe (CERC), Zagreb, November 13-15, Problem K