← 返回题目列表

Codeforces · 627/F

F. 岛屿之谜

中文机器翻译题面 查看原题

一个偏远岛链包含 n 个岛屿,它们之间有一些双向桥梁。当前的桥接网络形成一棵树。换句话说,共有 n - 1 座桥梁连接成对的岛屿,使得可以使用桥梁网络从任何其他岛屿到达任何岛屿。每个岛屿的中心都有一个相同的基座,除了一个岛屿之外,所有岛屿的基座上目前都放置着一座脆弱的、颜色独特的雕像。剩下的岛屿只有一个空基座。

岛民想要以新的顺序重新排列雕像。为此,他们重复以下过程:首先,他们选择一个与包含空基座的岛屿直接相邻的岛屿。然后,他们煞费苦心地将这座岛上的雕像抬过毗邻的桥,并将其放置在空的基座上。

仅使用上述操作通常不可能按所需顺序重新排列雕像。岛民希望再建造一座桥梁,以便以尽可能少的移动次数实现这一目标。找到要建造的桥梁以及将雕像排列到所需位置所需的最少雕像移动次数。

输入

第一行包含一个整数 n (2 ≤ n ≤ 200 000) — 岛屿总数。

第二行包含 n 个空格分隔的整数 ai (0 ≤ ai ≤ n - 1) — 当前位于第 i 个岛上的雕像。如果ai = 0,则岛上没有雕像。保证ai是不同的。

第三行包含 n 个空格分隔的整数 bi (0 ≤ bi ≤ n - 1) — 第 i 个岛屿所需的雕像。再次,bi = 0 表示该岛不需要雕像。保证bi是不同的。

接下来的 n - 1 行每行包含两个不同的空格分隔整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 第 i 个桥的端点。桥形成一棵树,并且保证没有桥在输入中被列出两次。

输出

打印单行整数:

如果重排可以在现有网络中完成,则输出 0 t,其中 t 是执行重排所需的移动次数。

否则,打印 u、v 和 t (1 ≤ u < v ≤ n) — 新桥的两个端点,以及执行重新排列所需的最小雕像移动次数。

如果无论如何构建新桥都无法完成重新排列,请打印包含 - 1 的单行。

示例

输入 #1

3
1 0 2
2 0 1
1 2
2 3

输出 #1

1 3 3

输入 #2

2
1 0
0 1
1 2

输出 #2

0 1

输入 #3

4
0 1 2 3
0 2 3 1
1 2
1 3
1 4

输出 #3

-1

注意

在第一个示例中,岛民可以建造一座连接岛屿 1 和岛屿 3 的桥梁,然后进行以下移动顺序:首先将雕像 1 从岛 1 移动到岛 2,然后将雕像 2 从岛 3 移动到岛 1,最后将雕像 1 从岛 2 移动到岛 3,总共移动 3 次。

在第二个示例中,岛民可以简单地将雕像 1 从岛 1 移动到岛 2。不需要建造新的桥梁,只需要进行 1 次移动。

在第三个示例中,没有添加桥接和后续移动会导致所需的位置。