Post Office

문제

In the JOI country, there are $NN$ post offices, numbered from $11$ to $NN$. Each post office has an assigned ”destination,” and the destination of post office $ii$ is post office $P_{i}P\_i$. Note that it is possible for $P_i=iP\_i\; =\; i$. If a package is sent from post office $ii$ at time $tt$, it will arrive at post office $P_{i}P\_i$ at time $t+1t\; +\; 1$. However, a post office cannot send another package while it is in the process of sending a package. Each post office can store an unlimited number of packages at any given time.

Now, $MM$ packages need to be delivered in the JOI country. The $jj$-th package arrives at post office $A_{j}A\_j$ at time $00$, and it must eventually be delivered to the assigned post office $B_{j}B\_j$. Given the information about the post offices and the packages, write a program to determine whether it is possible to deliver all the packages to their assigned post offices, and if so, find the smallest possible time at which the last package arrives at its assigned post office.

입력

Read the following data from the standard input.

$NN$

$P_{1}P\_1$ $P_{2}P\_2$ $\cdots \backslash cdots$ $P_{N}P\_N$

$MM$

$A_{1}A\_1$ $B_{1}B\_1$

$A_{2}A\_2$ $B_{2}B\_2$

$\mathrm{⋮}\backslash vdots$

$A_{M}A\_M$ $B_{M}B\_M$

출력

Output a single line to the standard output. If it is possible to deliver all the packages to their assigned post offices, output the smallest possible time at which the last package arrives at its assigned post office. Otherwise, output -1 instead.