G - Typical Path Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

N 頂点 M 辺の連結な単純無向グラフ G が与えられます。
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 の辺に向きが無いことをいいます。
グラフ G が単純であるとは、G が自己ループや多重辺を含まないことをいいます。
グラフ G が連結であるとは、G に含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
頂点 Z を経由する単純パスとは グラフ G 上の頂点 X,Y について、頂点 X と頂点 Y を結ぶ単純パスとは、相異なる頂点列 (v_1,v_2,\ldots,v_k) であって、v_1=X, v_k=Y かつ 任意の 1\leq i\leq k-1 をみたす整数 i について、頂点 v_i と頂点 v_{i+1} を結ぶ辺が G 上に存在するようなものを指します。
また、単純パス (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

頂点 3 を経由して頂点 1 と頂点 2 を結ぶ単純パスとしては、頂点 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

Score : 575 points

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