グラフ上で2つの頂点は到達可能か？
与えられたのは、頂点数
v と辺数 e を持つ無向グラフです。このグラフにおいて、q 個のクエリが与えられます。各クエリでは、ある2つの頂点が「到達可能」かどうか、すなわち一方の頂点からもう一方の頂点へグラフ上を辿って移動できるかをチェックします。入力
最初の行には、整数
v (1 ≤ v ≤ 1000) と e (1 ≤ e ≤ 1000) が与えられます。続く
e 行には、それぞれ v1, v2 (1 ≤ v1, v2 ≤ v) が書かれており、これは頂点 v1 と頂点 v2 が相互に接続されていることを示します。次の行にはクエリの数
q (1 ≤ q ≤ 100) が1つ与えられます。続く
q 行には、それぞれクエリとして、頂点 q1, q2 (1 ≤ q1, q2 ≤ v) のペアが与えられます。出力
各クエリに対して、頂点
q1 から q2 に到達できるなら Yes、到達できないなら No を出力してください。例
入力 | 出力 |
7 6
1 2
2 3
1 3
4 5
5 6
4 6
4
1 2
2 5
3 6
4 6 | Yes
No
No
Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB