CF929D Пограничные врата

英雄阿尔卡季站在一条狭窄的土地带上，这条土地被分为 $n$ 个区域，编号从 $1$ 到 $n$。从第 $i$ 个区域只能前往第 $(i-1)$ 个区域和第 $(i+1)$ 个区域（如果它们存在）。每对相邻区域之间有一道边境之门，这道门有不同的颜色，第 $i$ 个区域和第 $i+1$ 个区域之间的门的颜色为 $g_{i}$。 阿尔卡季只有在之前去过某个拥有该颜色钥匙的守护者帐篷并拿到钥匙后，才能通过某种颜色的边境之门。每个区域里恰好有一个守护者帐篷，帐篷的颜色为 $k_{i}$，表示第 $i$ 个区域的帐篷颜色。阿尔卡季访问某种颜色的帐篷后，可以无限次通过所有该颜色的门。 通过一道门需要花费一次行动，访问帐篷和其他移动不需要消耗行动。请问阿尔卡季从区域 $a$ 到区域 $b$，在最初没有任何钥匙的情况下，最少需要多少次行动？

第一行包含三个整数 $n$、$a$、$b$（$2 \leq n \leq 100000$，$1 \leq a, b \leq n$，$a \neq b$）——区域数、起始区域编号和目标区域编号。 第二行包含 $n-1$ 个整数 $g_{1}, g_{2}, ..., g_{n-1}$（$1 \leq g_{i} \leq 100000$），其中 $g_{i}$ 表示第 $i$ 个区域和第 $i+1$ 个区域之间的门的颜色。 第三行包含 $n$ 个整数 $k_{1}, k_{2}, ..., k_{n}$（$1 \leq k_{i} \leq 100000$），其中 $k_{i}$ 表示第 $i$ 个区域守护者帐篷的颜色。

如果阿尔卡季无法从区域 $a$ 到达区域 $b$，输出 $-1$。 否则，输出阿尔卡季所需的最小行动次数。

由 ChatGPT 4.1 翻译