AT_abc021_b.[ABC021B] 嘘つきの高橋くん

你和高桥君住在 AtCoder 王国。AtCoder 王国有 $N$ 个城镇，以及若干条连接城镇之间的道路，道路是双向通行的。$N$ 个城镇分别被称为城镇 $1$、城镇 $2$、……、城镇 $N$。

高桥君决定去你家玩。他从城镇 $a$ 出发，经过 AtCoder 王国的某些城镇，恰好经过 $K$ 次后，抵达你家所在的城镇 $b$。

高桥君声称他是沿着从 $a$ 到 $b$ 的最短路径前来的，但你觉得他可能在说谎。然而，你完全不知道城镇之间道路的具体连接方式，因此无法直接判断高桥君所走的路线是否为最短路径。

你成功地问出了高桥君经过的城镇的顺序，但这个信息不包括出发地 $a$ 和终点 $b$。

请你根据这些信息，编写一个程序判断高桥君是否有可能是沿着最短路径移动的。这里，从 $a$ 到 $b$ 的最短路径指的是经过的道路数最少的路径。

如果存在至少一种城镇和道路的连接方式，使得高桥君所走的路径是最短路径，则输出“YES”；否则输出“NO”。

输入按以下格式从标准输入读入。

$N$ $a$ $b$ $K$ $P_1$ $P_2$ … $P_K$

• 第 $1$ 行给出 AtCoder 王国中城镇的数量 $N$，满足 $2 \leq N \leq 100$。
• 第 $2$ 行给出高桥君出发的城镇和你家所在城镇的编号 $a, b$，满足 $1 \leq a, b \leq N$，且 $a \neq b$。
• 第 $3$ 行给出高桥君移动过程中经过的城镇数 $K$，满足 $1 \leq K \leq 100$。
• 第 $4$ 行给出高桥君移动过程中依次经过的城镇编号，空格分隔。第 $i$ 个数 $P_i$ 表示高桥君从 $a$ 出发后第 $i$ 个经过的城镇编号，$1 \leq P_i \leq N$。
• 相邻的 $P_i$ 必然不同，即对于所有 $j$（$2 \leq j \leq K$），都有 $P_j \neq P_{j-1}$。此外，$P_1 \neq a$ 且 $P_K \neq b$。

输出一行。如果高桥君有可能是沿着最短路径移动的，输出 YES；否则输出 NO。

注意输出末尾需要换行。

样例解释 1

例如，考虑如下道路结构，则 $1 \to 3 \to 4 \to 2 \to 5$ 这条路径就是最短路径。

样例解释 2

不存在任何一种道路结构，使得 $1 \to 2 \to 4 \to 2 \to 7 \to 3$ 这条路径为最短路径。因为无论道路如何连接，路径中如果有重复经过某个城镇，总可以省略这些重复，从而得到更短的路径。

样例解释 3

路径为 $1 \to 2 \to 1 \to 3 \to 4$，即途中又回到了出发点。这样就不可能是最短路径。

样例解释 4

路径为 $1 \to 2 \to 4 \to 3 \to 4$，即途中已经到达终点却又离开了终点。

由 ChatGPT 4.1 翻译