CF627F.Island Puzzle

A remote island chain contains n islands, with some bidirectional bridges between them. The current bridge network forms a tree. In other words, a total of n - 1 bridges connect pairs of islands in a way that it's possible to reach any island from any other island using the bridge network. The center of each island contains an identical pedestal, and all but one of the islands has a fragile, uniquely colored statue currently held on the pedestal. The remaining island holds only an empty pedestal.

The islanders want to rearrange the statues in a new order. To do this, they repeat the following process: first, they choose an island directly adjacent to the island containing an empty pedestal. Then, they painstakingly carry the statue on this island across the adjoining bridge and place it on the empty pedestal.

It is often impossible to rearrange statues in the desired order using only the operation described above. The islanders would like to build one additional bridge in order to make this achievable in the fewest number of movements possible. Find the bridge to construct and the minimum number of statue movements necessary to arrange the statues in the desired position.

一个遥远的群岛链包含 $n$ 个岛屿，岛屿之间由若干双向桥梁连接。当前的桥梁网络构成一棵树。换言之，恰好有 $n-1$ 座桥梁将岛屿两两相连，使得任意两个岛屿之间均可通过桥梁网络相互抵达。每个岛屿的中心都设有一个完全相同的基座，除一座岛屿外，其余所有岛屿的基座上均放置着一座易碎的、颜色互不相同的雕像；剩下那座岛屿的基座则为空。

岛民希望将雕像重新排列成一种新的顺序。为此，他们反复执行如下操作：首先，选择一个与空基座所在岛屿直接相邻的岛屿；然后，小心翼翼地将该岛屿基座上的雕像经由相连的桥梁搬运至空基座上。

仅使用上述操作，常常无法将雕像排列成所期望的顺序。岛民希望额外修建一座桥梁，使得目标排列可通过尽可能少的雕像移动步数实现。请找出应修建的桥梁（即应连接的两个岛屿），并求出达成目标排列所需的最少雕像移动步数。

The first line contains a single integer n (2 ≤ n ≤ 200 000) — the total number of islands.

The second line contains n space-separated integers a__i (0 ≤ a__i ≤ n - 1) — the statue currently located on the i-th island. If a__i = 0, then the island has no statue. It is guaranteed that the a__i are distinct.

The third line contains n space-separated integers b__i (0 ≤ b__i ≤ n - 1) — the desired statues of the i-th island. Once again, b__i = 0 indicates the island desires no statue. It is guaranteed that the b__i are distinct.

The next n - 1 lines each contain two distinct space-separated integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — the endpoints of the i-th bridge. Bridges form a tree, and it is guaranteed that no bridge is listed twice in the input.

第一行包含一个整数 $n$（$2 \leq n \leq 200\,000$）—— 岛屿的总数。

第二行包含 $n$ 个以空格分隔的整数 $a_i$（$0 \leq a_i \leq n - 1$）—— 当前位于第 $i$ 座岛屿上的雕像编号。若 $a_i = 0$，则表示该岛屿上没有雕像。保证所有 $a_i$ 互不相同。

第三行包含 $n$ 个以空格分隔的整数 $b_i$（$0 \leq b_i \leq n - 1$）—— 第 $i$ 座岛屿期望拥有的雕像编号。同样地，$b_i = 0$ 表示该岛屿不希望拥有任何雕像。保证所有 $b_i$ 互不相同。

接下来的 $n - 1$ 行，每行包含两个以空格分隔的互异整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$）—— 第 $i$ 座桥的两个端点。这些桥构成一棵树，且保证输入中不会重复列出同一条桥。

Print a single line of integers:

If the rearrangement can be done in the existing network, output 0 t, where t is the number of moves necessary to perform the rearrangement.

Otherwise, print u, v, and t (1 ≤ u < v ≤ n) — the two endpoints of the new bridge, and the minimum number of statue movements needed to perform the rearrangement.

If the rearrangement cannot be done no matter how the new bridge is built, print a single line containing  - 1.

输出一行整数：

• 如果可以在现有网络中完成重排，则输出 0 t，其中 t 是完成重排所需的移动步数；
• 否则，输出 u、v 和 t（满足 $1 \le u < v \le n$），即新建桥梁的两个端点，以及完成重排所需的最少雕像移动次数；
• 如果无论怎样修建新桥都无法完成重排，则输出单独一行 -1。

In the first sample, the islanders can build a bridge connecting islands 1 and 3 and then make the following sequence of moves: first move statue 1 from island 1 to island 2, then move statue 2 from island 3 to island 1, and finally move statue 1 from island 2 to island 3 for a total of 3 moves.

In the second sample, the islanders can simply move statue 1 from island 1 to island 2. No new bridges need to be built and only 1 move needs to be made.

In the third sample, no added bridge and subsequent movements result in the desired position.

在第一个样例中，岛民可以建造一座连接岛屿 1 和岛屿 3 的桥，然后执行以下移动序列：首先将雕像 1 从岛屿 1 移动到岛屿 2，接着将雕像 2 从岛屿 3 移动到岛屿 1，最后将雕像 1 从岛屿 2 移动到岛屿 3，总共需要 3 次移动。

在第二个样例中，岛民只需将雕像 1 从岛屿 1 移动到岛屿 2 即可。无需新建桥梁，仅需 1 次移动。

在第三个样例中，无论是否新增桥梁并进行后续移动，都无法达到目标布局。