[PA 2020] Bardzo skomplikowany test

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Bardzo skomplikowany test](https://sio2.mimuw.edu.pl/c/pa-2020-1/bst/)** Bytie 刚刚参加了算法和数据结构这门课的面试。他没有为之学习太长时间，所以他做得不是太好。经过几分钟的交谈，这位心碎的主讲老师决定给这个男孩最后一次机会。 - 「孩儿，你知道啥是 BST 不？」教授问 Bytie 听到这句话后内心狂喜，因为在他上课睡觉的时候记住了一些理论。 - 「知道。大小为 $n$ 的 BST 是一棵有根树，其顶点用 $1$ 到 $n$ 的整数来编号。每个节点最多可以有两个子节点；它可以有一个最多一个左子节点和一个最多一个右子节点。此外，每个节点的编号必须大于其左子树中所有节点的编号，并小于其右子树中所有顶点的编号。」Bytie 回答说，他达到了他潜意识的深处。 - 「很好。让我们看看你是否记住了如何对 BST 进行旋转。」一直坐在那里的教授回答说。他站起来，向黑板走去。 Bytie 被冷汗浸透了。他一时失去了信心，因为他记不起旋转的具体原理（可能在上这节课的时候，他正在另一边摸鱼，没听课）。考官在黑板上画了两棵同样大小的 BST 树，并让 Bytie 用正确的旋转将第一棵树转化为第二棵树。 Bytie 想了一会儿，认为左旋就是选择某个节点 $v$ 和它的右子节点 $w$，并让 $w$ 成为 $v$ 的父节点。Bytie 的直觉用以下伪代码描述。 ``` 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 ```  以此类推，Bytie 理解了右旋，其中 $w$ 是 $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 ```  然而，Bytie 很快就注意到有些不对劲。如果节点 $w$ 在左旋时有左子树，它就会丢失！同样在右转过程中，节点 $w$ 的右子树也会丢失。 - 「快点孩儿，你不是唯一一个想通过这次考试的人。」教授不耐烦地催促道。 在没有太多时间考虑的情况下，Bytie 假设只有在这个有问题的子树是空的情况下才能执行旋转，也就是说，如果没有顶点丢失并且树保持一致的话才进行旋转。 为了尽快结束他的煎熬，他决定进行最少次数的旋转，使他能够将第一棵树变成第二棵。请告诉他这是否可行，如果可行，他需要进行多少次轮换？由于这个数字可能相当大，请告诉他这个值对 $10^9+7$ 取模后的值。 ## Input 第一行包含一个整数 $n$，表示这个 BST 的大小。 接下来两行描述这两棵树。对于一棵树用一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 描述。如果 $a_i\ge 1$，表示 $i$ 节点的父节点；如果 $a_i=-1$，则表示这是树的根节点。 你可以假设这两棵树都是合法的 BST，即树中没有环，恰好有一个根节点，每个节点最多只有一个比自己小的子节点和一个比自己大的子节点。 ## Output 输出应该包含一个整数，表示用 Bytie 的方式把第一棵树转化为第二棵树所需最少旋转次数对 $10^9+7$ 取模后的值，如果不可能转化，输出 $-1$。 [samples] ## Note #### 样例 1 解释 下图展示了旋转最小次数所采取的旋转方式。  ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$-1\le a_i\le n$，$a_i\neq 0$。