一个偏远岛链包含 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。
在第三个示例中,没有任何运动序列会导致所需的位置。