分数: 575 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。
的顶点和边 G 被编号为顶点 1,顶点 2, \ldots,顶点 N,和边缘 1,边缘 2, \ldots,边缘 M分别和边 i (1\leq i\leq M) 连接顶点 U_i 和 V_i.
您还获得了不同的顶点 A,B,C on G。 判断是否存在连接顶点的简单路径 A 和 C 通过顶点 B.
什么是简单连通无向图?
图表 G 被认为是一个简单的连通无向图,当 G 是一个简单且连通的无向图。图表 G 被称为无向图,当 G 没有方向。
图表 G 很简单,当 G 不包含自环或多边。 当可以在 的所有顶点之间移动时,
图表 G 已连接 G 通过边缘。
什么是通过顶点的简单路径 Z?
对于顶点 图表上的 X 和 Y 在图表上 G,一个简单的连接路径 X 和 Y 是一系列不同的顶点 (v_1,v_2,\ldots,v_k) 这样 v_1=X, v_k=Y,并且对于每个整数 i 满意 1\leq i\leq k-1,有一个边缘 G 连接顶点 v_i 和 v_{i+1}.一条简单的路径 (v_1,v_2,\ldots,v_k) 据说是通过顶点 Z 当有 i (2\leq i\leq k-1) 满意 v_i=Z.
约束
- 3 \leq N \leq 2\times 10^5
- N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right)
- 1\leq A,B,C\leq N
- A, B,和 C 都是不同的。
- 1\leq U_i<V_i\leq N
- 对 (U_i,V_i) 都是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A B C U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
如果存在满足语句中条件的简单路径,则打印 Yes;否则,打印 No.
示例输入 1
6 7 1 3 2 1 2 1 5 2 3 2 5 2 6 3 4 4 5
示例输出 1
Yes
连接顶点的一条简单路径 1 和 2 通过顶点 3 is 1 \to 5 \to 4 \to 3 \to 2.
因此,打印 Yes.
示例输入 2
6 6 1 3 2 1 2 2 3 2 5 2 6 3 4 4 5
示例输出 2
No
没有简单路径满足条件。因此,打印 No.
示例输入 3
3 2 1 3 2 1 2 2 3
示例输出 3
No