典型路径问题

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。

$G$ 的顶点编号为顶点 $1$、顶点 $2$、$\dots$、顶点 $N$,边编号为边 $1$、边 $2$、$\dots$、边 $M$,边 $i$($1 \le i \le M$)连接顶点 $U_i$ 和顶点 $V_i$。

另外,给出 $G$ 上两两不同的顶点 $A$、$B$、$C$。

判断是否存在连接顶点 $A$ 和顶点 $C$ 且经过顶点 $B$ 的简单路径。

什么是简单连通无向图?

当 $G$ 是无向图且简单、连通时,称 $G$ 为简单连通无向图。

当 $G$ 的边没有方向时,称 $G$ 为无向图。

当 $G$ 不含自环和重边时,称 $G$ 是简单的。

当可以通过边在 $G$ 的所有顶点之间往返时,称 $G$ 是连通的。

什么是经过顶点 $Z$ 的简单路径?

对于图 $G$ 上的顶点 $X$ 和 $Y$,连接 $X$ 和 $Y$ 的简单路径是满足以下条件的互不相同的顶点序列 $(v_1,v_2,\dots,v_k)$:$v_1=X$,$v_k=Y$,且对于满足 $1 \le i \le k-1$ 的每个整数 $i$,图 $G$ 中存在连接顶点 $v_i$ 和顶点 $v_{i+1}$ 的边。

当存在满足 $v_i=Z$ 的 $i$($2 \le i \le k-1$)时,称简单路径 $(v_1,v_2,\dots,v_k)$ 经过顶点 $Z$。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$A$ $B$ $C$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

输出格式

若存在满足题目所述条件的简单路径,输出 Yes;否则,输出 No。

样例

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

Yes

一条连接顶点 $1$ 和顶点 $2$ 且经过顶点 $3$ 的简单路径为 $1 \to 5 \to 4 \to 3 \to 2$。

因此,输出 Yes。

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

No

不存在满足条件的简单路径。因此,输出 No。

3 2
1 3 2
1 2
2 3

No

数据范围

• $3 \le N \le 2 \times 10^5$
• $N-1 \le M \le \min\left(\frac{N(N-1)}{2},2 \times 10^5\right)$
• $1 \le A,B,C \le N$
• $A$、$B$、$C$ 两两不同。
• $1 \le U_i \lt V_i \le N$
• 所有 $(U_i,V_i)$ 两两不同。
• 所有输入值均为整数。