Score : $575$ points

问题描述

你被给定一个简单的连通无向图 $G$，其中包含 $N$ 个顶点和 $M$ 条边。 图 $G$ 中的顶点和边分别标记为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$，以及边 $1$、边 $2$、$\ldots$、边 $M$，其中第 $i$ 条边 $(1\leq i\leq M)$ 连接顶点 $U_i$ 和顶点 $V_i$。

另外，你还被赋予了图 $G$ 上互不相同的三个顶点 $A$、$B$ 和 $C$。你需要确定是否存在一条通过顶点 $B$ 连接顶点 $A$ 和顶点 $C$ 的简单路径。

什么是简单连通无向图？若一个图 $G$ 是无向且既是简单图又是连通图，则称其为简单连通无向图。
若图 $G$ 的边没有方向，则称其为无向图。
若图 $G$ 不包含自环和平行边，则称其为简单图。
若在图 $G$ 中可以通过边从所有顶点的一个到达另一个，则称其为连通图。什么是通过顶点 $Z$ 的简单路径？对于图 $G$ 上的顶点 $X$ 和 $Y$，连接 $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}$ 的边。
如果对于某个 $i$ $(2\leq i\leq k-1)$ 满足 $v_i=Z$，则称该简单路径 $(v_1,v_2,\ldots,v_k)$ 是通过顶点 $Z$ 的路径。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges.
The vertices and edges of $G$ are numbered as vertex $1$, vertex $2$, $\ldots$, vertex $N$, and edge $1$, edge $2$, $\ldots$, edge $M$, respectively, and edge $i$ $(1\leq i\leq M)$ connects vertices $U_i$ and $V_i$.

You are also given distinct vertices $A,B,C$ on $G$. Determine if there is a simple path connecting vertices $A$ and $C$ via vertex $B$.

What is a simple connected undirected graph? A graph $G$ is said to be a simple connected undirected graph when $G$ is an undirected graph that is simple and connected.
A graph $G$ is said to be an undirected graph when the edges of $G$ have no direction.
A graph $G$ is simple when $G$ does not contain self-loops or multi-edges.
A graph $G$ is connected when one can travel between all vertices of $G$ via edges. What is a simple path via vertex $Z$? For vertices $X$ and $Y$ on a graph $G$, a simple path connecting $X$ and $Y$ is a sequence of distinct vertices $(v_1,v_2,\ldots,v_k)$ such that $v_1=X$, $v_k=Y$, and for every integer $i$ satisfying $1\leq i\leq k-1$, there is an edge on $G$ connecting vertices $v_i$ and $v_{i+1}$.
A simple path $(v_1,v_2,\ldots,v_k)$ is said to be via vertex $Z$ when there is an $i$ $(2\leq i\leq k-1)$ satisfying $v_i=Z$.

Constraints

• $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$, and $C$ are all distinct.
• $1\leq U_i<V_i\leq N$
• The pairs $(U_i,V_i)$ are all distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A$ $B$ $C$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

Output

If there is a simple path that satisfies the condition in the statement, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

One simple path connecting vertices $1$ and $2$ via vertex $3$ is $1$ $\to$ $5$ $\to$ $4$ $\to$ $3$ $\to$ $2$.

Thus, print Yes.

Sample Input 2

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

Sample Output 2

No

No simple path satisfies the condition. Thus, print No.

Sample Input 3

3 2
1 3 2
1 2
2 3

Sample Output 3

No

update @ 2024/3/10 09:05:42