← 返回题目列表

Codeforces · 929/D

D. 关闭

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

英雄阿尔卡迪位于一片狭长的土地上,分为n个区域,编号从1到n。从第 i 个区域,您只能前往第 (i - 1) 个区域和第 (i + 1) 个区域(如果存在)。此外,每对相邻区域之间都有边境门,边境门可以是不同颜色的;第 i 个区域和第 (i + 1) 个区域之间的门的颜色等于 gi。

阿尔卡迪只有在之前访问过某个颜色的钥匙保管人的帐篷并拿走钥匙后,才能通过该颜色的边境大门。每个区域恰好包含一个特定颜色的钥匙保管员帐篷;第 i 个区域的帐篷颜色为 ki。参观完某种颜色的帐篷后,阿尔卡迪可以无限次地穿过该颜色的任意门。

阿尔卡季花费一招穿过一扇门;参观帐篷等活动不需要任何动作。如果阿尔卡迪最初没有任何钥匙,他最少需要多少步才能从 a 区到达 b 区?

输入

第一行包含三个整数 n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — 分别是区域数量、起始区域编号和结束区域编号。

第二行包含 n - 1 个整数 g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100,000),其中 gi 是区域 i 和 i + 1 之间的边境门的颜色。

第三行包含n个整数k1, k2, ..., kn (1 ≤ ki ≤ 100 000),其中ki表示第i个区域中钥匙保管员帐篷的颜色。

输出

如果Arkady 在没有钥匙的情况下无法从a 区到达b 区,则打印-1。

否则打印 Arkady 需要的最小步数。

示例

输入 #1

5 4 1
3 1 1 2
7 1 2 1 3

输出 #1

7

输入 #2

5 1 5
4 3 2 1
4 3 2 5 5

输出 #2

-1

注意

在第一个示例中,为了从区域 4 到达区域 1,Arkady 必须首先拿到颜色 1 的钥匙,进入区域 3,在那里拿到颜色 2 的钥匙,然后回到区域 4,然后到区域 5,在那里拿到颜色 3 的钥匙,并在四步内到达区域 1。

在第二个例子中,Arkady 只能到达第四个区域,因为根本没有颜色 1 的钥匙保管员帐篷。