매우 복잡한 테스트

Bajtek은 알고리즘과 자료구조 구술 시험을 보고 있다. 공부를 충분히 하지 못해서 상황이 좋지 않다. 몇 분간 대화를 나눈 뒤 지친 교수가 마지막 기회를 주기로 한다.

"BST 트리가 무엇인지 아니?" 교수가 물었다.

Bajtek은 강의 중 졸다가 들은 내용이 떠올라 빙긋 웃었다.

"응. 크기가 n인 BST 트리는 정점에 1부터 n까지의 정수가 번호로 붙은 루트 있는 트리다. 각 정점은 자식을 최대 두 개까지 가질 수 있다. 왼쪽 자식은 최대 한 명, 오른쪽 자식도 최대 한 명이다. 또한 각 정점의 번호는 왼쪽 부분 트리에 있는 모든 정점의 번호보다 커야 하고, 오른쪽 부분 트리에 있는 모든 정점의 번호보다 작아야 한다." Bajtek이 무의식 깊은 곳에서 끌어내어 답했다.

"좋아. 회전을 어떻게 하는지 기억하는지 확인해 보지." 앉아 있던 교수가 일어나 칠판 쪽으로 걸어간다.

Bajtek은 식은땀이 났다. 회전이 정확히 어떻게 작동하는지 기억나지 않았다. 아마 강의의 그 부분에서 다른 쪽으로 돌아누웠고, 그 바람에 교수의 말이 묻힌 모양이다. 시험관은 칠판에 같은 크기의 BST 트리 두 개를 그리고, 올바른 회전으로 첫 번째 트리를 두 번째 트리로 바꾸라고 지시했다.

Bajtek은 잠시 생각하고 왼쪽 회전을, 정점 v와 그 오른쪽 자식 w를 고른 뒤 w를 v의 부모로 만드는 것이라고 정했다. 그의 직관은 다음 의사코드로 정리된다.

if v.Ojciec != null then
    if v.Ojciec.PrawySyn == v then
        v.Ojciec.PrawySyn := w
    else
        v.Ojciec.LewySyn := w
w.Ojciec := v.Ojciec
v.Ojciec := w
w.LewySyn := v
v.PrawySyn := null

Bajtek은 오른쪽 회전도 같은 방식으로 이해한다. 이때 w는 v의 왼쪽 자식이다.

if v.Ojciec != null then
    if v.Ojciec.PrawySyn == v then
        v.Ojciec.PrawySyn := w
    else
        v.Ojciec.LewySyn := w
w.Ojciec := v.Ojciec
v.Ojciec := w
w.PrawySyn := v
v.LewySyn := null

하지만 소년은 곧 문제를 알아챈다. 왼쪽 회전 때 w에 왼쪽 부분 트리가 있으면 그 부분 트리가 사라진다. 마찬가지로 오른쪽 회전 때는 w의 오른쪽 부분 트리가 사라질 수 있다.

"서두르게, 자네만 이 시험에 붙고 싶은 게 아니야." 참을성을 잃은 교수가 재촉한다.

시간이 많지 않아서 Bajtek은 문제가 되는 부분 트리가 비어 있을 때에만 회전할 수 있다고 정했다. 즉 어떤 정점도 잃지 않고 트리가 연결된 상태로 남을 때에만 회전한다.

가능한 한 빨리 이 고통을 끝내려고 Bajtek은 첫 번째 트리를 두 번째 트리로 바꾸는 데 필요한 회전 횟수를 최소로 하기로 했다. 이것이 가능한지, 가능하다면 몇 번의 회전이 필요한지 판단할 수 있겠는가? 이 수가 클 수 있으므로 $10^9 + 7$로 나눈 나머지만 구하면 된다.

첫 줄에는 교수가 그린 트리의 크기 n ($1 \le n \le 5 \times 10^5$) 이 정수 하나로 주어진다.

다음 두 줄에는 두 트리의 설명이 주어진다. 한 설명은 n개의 정수 $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le n$, $a_i \ne 0$) 으로 이루어진다. $a_i \ge 1$ 이면 i번 정점의 부모가 $a_i$번 정점이라는 뜻이다. $a_i = -1$ 이면 i번 정점이 트리 전체의 루트라는 뜻이다.

두 트리가 올바른 BST 트리라고 가정해도 된다. 즉 사이클이 없고, 루트는 정확히 하나이며, 각 정점은 자신보다 작은 자식과 큰 자식을 각각 최대 하나씩 가지고, 위에서 말한 부분 트리 조건이 성립한다.

첫 번째 트리를 두 번째 트리로 바꾸는 데 필요한 최소 회전 횟수(Bajtek의 정의에 따른 회전)를 $10^9 + 7$로 나눈 나머지를 정수 하나로 출력한다. 그런 변환이 불가능하면 -1을 출력한다.

아래 그림은 트리를 변환하는 최소 회전 횟수를 보여 준다.