← 返回题目列表

Codeforces · 634/A

A. 岛屿之谜

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

一个偏远岛链包含 n 个岛屿,标记为 1 到 n。双向桥梁连接岛屿,形成一个简单的循环 - 一座桥梁连接岛屿 1 和 2、岛屿 2 和 3 等,另外还有一座桥梁连接岛屿 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是不同的。

输出

如果可以在现有网络中进行重新排列,则打印“YES”(不带引号),否则打印“NO”。

示例

输入 #1

3
1 0 2
2 0 1

输出 #1

YES

输入 #2

2
1 0
0 1

输出 #2

YES

输入 #3

4
1 2 3 0
0 3 2 1

输出 #3

NO

注意

在第一个示例中,岛民可以首先将雕像 1 从岛 1 移动到岛 2,然后将雕像 2 从岛 3 移动到岛 1,最后将雕像 1 从岛 2 移动到岛 3。

在第二个示例中,岛民可以简单地将雕像 1 从岛 1 移动到岛 2。

在第三个示例中,没有任何运动序列会导致所需的位置。