K. Roses
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Roses really smell like poopoo.

One afternoon, "Andre 3000" and "Big Boi" decided to go outside and pick roses. There are $$$n$$$ roses indexed $$$0$$$ through $$$n-1$$$. Both Andre 3000 and Big Boi decide that certain roses will smell good if picked after others. Their actions can be represented by two arrays given in the input, $$$a$$$ and $$$b$$$.

Specifically, after picking rose $$$i$$$, Andre 3000 will look at $$$a_i$$$. If $$$a_i$$$ is $$$-1$$$, he will stop picking roses. Otherwise, he will pick rose $$$a_i$$$ $$$(a_i \gt i)$$$. Likewise, after picking rose $$$i$$$, Big Boi will stop picking roses if $$$b_i = -1$$$, otherwise he will pick rose $$$b_i$$$ $$$(b_i \gt i)$$$.

Andre 3000 and Big Boi will both start by initially picking the same rose and want to know if it is possible that they will ever pick the same rose again. If this is the case for some initial rose picked by both Andre 3000 and Big Boi, print that initial rose's index. Otherwise, print $$$-1$$$. If there are multiple solutions, you can print any.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$. The next line contains $$$n$$$ integers where the $$$i$$$-th integer is $$$a_i$$$ $$$(a_i = -1$$$ OR $$$i \lt a_i \lt n)$$$. The next line contains $$$N$$$ integers where the $$$i$$$-th integer is $$$b_i$$$ $$$(b_i = -1$$$ OR $$$i \lt b_i \lt n)$$$.

Output

Print the index of any rose such that if both Andre 3000 and Big Boi start by picking that rose, there exists another different rose such that they will both eventually pick that other rose too. If no such initial rose exists, print $$$-1$$$.

Examples
Input
5
1 3 -1 4 -1
2 4 3 -1 -1
Output
0
Input
4
1 2 -1 -1
3 3 -1 -1
Output
-1
Note

In the first example, let's say Andre 3000 and Big Boi both start by picking rose $$$0$$$. After picking rose $$$0$$$, Andre 3000 will pick rose $$$1$$$ then $$$3$$$ then $$$4$$$ and then will stop picking roses. After picking rose $$$0$$$, Big Boi will pick rose $$$2$$$ then $$$3$$$ then stop picking roses. Since, both Andre 3000 and Big Boi pick rose $$$3$$$ some point after both starting by picking rose $$$0$$$, rose $$$0$$$ is a valid starting rose.

In the second example, it can be seen that there is no rose such that if both Andre 3000 and Big Boi start by picking that rose, there exists another different rose such that they will both eventually pick that other rose too.

Problem Credits: Eric Yachbes