閉路の判定 C編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

1, ..., n の番号のついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

m 本の枝が与えられます。この m 本の枝から構成される、閉路が存在しない無向グラフ G に枝 (c_j, d_j) (1 ≦ j ≦ q) を追加したグラフを G_j とします。G_j に閉路が存在するかどうか判定してください。G_j は、G に枝 (c_j, d_j) の 1 本のみを追加したグラフであり、G_{j-1} に枝 (c_j, d_j) を追加したグラフではないことに注意してください。

入力される値

n m q
a_1 b_1
...
a_m b_m
c_1 d_1
...
c_q d_q

・ 1 行目に、頂点の個数を表す n、枝の本数を表す m、調べるグラフの数を表す q が与えられます。
・ i + 1 行目に、グラフ G を構成する枝 i を表す頂点の組 (a_i, b_i) が与えられます。(1 ≦ i ≦ m)
・ j + m + 1 行目に、グラフ G_j を構成する枝 j を表す頂点の組 (c_j, d_j) が与えられます。(1 ≦ j ≦ q)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 q 行出力してください。j 行目に、グラフ G_j に閉路が存在するなら Yes、そうでなければ No と出力してください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100
・ 1 ≦ m ≦ n-1
・ 1 ≦ q ≦ n(n-1) / 2 - m
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ 1 ≦ c_j, d_j ≦ n (1 ≦ j ≦ q)
・ c_j ≠ d_j (1 ≦ j ≦ q)
・同じ頂点の組は 2 回以上入力されない
・グラフ G には閉路は存在しない

入力例1: 6 4 5
1 6
1 2
1 4
1 5
3 4
4 6
5 6
2 5
3 5

出力例1: No
Yes
Yes
Yes
No

入力例2: 8 7 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 8
4 6
5 7

出力例2: Yes
Yes
Yes

問題一覧へ戻る