Problem Description

This problem is translated from PA 2020 Round 5 Bardzo skomplikowany test.

Bytie has just attended an interview for the Algorithms and Data Structures course. He did not study for very long, so he did not do very well. After a few minutes of conversation, the disappointed lecturer decided to give the boy one last chance.

• “Kid, do you know what a BST is?” the professor asked.

Bytie was overjoyed, because he remembered some theory from when he slept in class.

• “Yes. A BST of size $n$ is a rooted tree whose vertices are numbered with the integers from $1$ to $n$. Each node can have at most two children: at most one left child and at most one right child. Also, the label of each node must be greater than the labels of all nodes in its left subtree, and smaller than the labels of all vertices in its right subtree.” Bytie replied, reaching deep into his subconscious.
• “Good. Let us see if you remember how to rotate a BST.” replied the professor, who had been sitting there all the time. He stood up and walked to the blackboard.

Bytie was drenched in cold sweat. He suddenly lost confidence, because he could not remember the exact rule of rotations (maybe he was slacking off and did not listen during this class). The examiner drew two BSTs of the same size on the blackboard and asked Bytie to transform the first tree into the second one using the correct rotations.

Bytie thought for a while and decided that a left rotation means choosing some node $v$ and its right child $w$, and making $w$ the parent of $v$. Bytie’s intuition can be described by the following pseudocode.

if v.Parent != null then
    if v.Parent.RightSon == v then
        v.Parent.RightSon := w
    else
        v.Parent.LeftSon := w
w.Parent := v.Parent
v.Parent := w
w.LeftSon := v
v.RightSon := null

Similarly, Bytie understood a right rotation, where $w$ is the left child of $v$.

if v.Parent != null then
    if v.Parent.RightSon == v then
        v.Parent.RightSon := w
    else
        v.Parent.LeftSon := w
w.Parent := v.Parent
v.Parent := w
w.RightSon := v
v.LeftSon := null

However, Bytie quickly noticed that something was wrong. If node $w$ has a left subtree during a left rotation, it will be lost. Likewise, during a right rotation, the right subtree of node $w$ will be lost.

• “Hurry up, kid, you are not the only one who wants to pass this exam.” the professor urged impatiently.

With no time to think too much, Bytie assumed that a rotation can be performed only when this problematic subtree is empty, that is, only if no vertices are lost and the tree remains consistent.

To end his suffering as soon as possible, he decided to perform the minimum number of rotations so that he can transform the first tree into the second one. Please tell him whether this is possible, and if so, how many rotations he needs to perform. Since this number may be quite large, output it modulo $10^9+7$.

Input Format

The first line contains an integer $n$, the size of the BST.

The next two lines describe the two trees. For each tree, one line contains $n$ integers $a_1, a_2, \cdots, a_n$. If $a_i \ge 1$, it means the parent of node $i$ is $a_i$. If $a_i = -1$, then node $i$ is the root of the tree.

You may assume that both trees are valid BSTs, i.e. there are no cycles, there is exactly one root, and each node has at most one child smaller than itself and at most one child larger than itself.

Output Format

Output one integer, the minimum number of rotations needed to transform the first tree into the second tree using Bytie’s method, modulo $10^9+7$. If it is impossible, output $-1$.

4
3 1 -1 3
2 -1 4 2

3

8
2 4 2 7 4 5 -1 7
2 3 6 5 3 -1 6 7

7

Hint

Explanation for Sample 1

The figure below shows how to achieve the minimum number of rotations.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 5 \times 10^5$, $-1 \le a_i \le n$, and $a_i \neq 0$.

Translated by ChatGPT 5