AT_agc077_c [AGC077C] Reverse and DAG

$ N $ 頂点 $ M $ 辺の単純有向グラフ $ G $ があります．頂点には $ 1 $ から $ N $ の番号が付いており， $ i $ 番目の辺は頂点 $ a_i $ から頂点 $ b_i $ へ張られています． $ i\neq j $ のとき $ (a_i,b_i)\neq (b_j,a_j) $ であることが保証されます．また $ 2 $ 以上 $ N-2 $ 以下の整数 $ K $ が与えられます． 以下の操作を $ 0 $ 回以上好きな回数行うことで， $ G $ を有向閉路を含まないグラフ（DAG）にできるか否かを判定してください． - $ \lbrace 1,\ldots,N\rbrace $ のサイズ $ K $ の部分集合 $ S $ を選ぶ．始点と終点の番号がともに $ S $ に含まれるような有向辺すべてについて，その向きを反転させる． - すなわち，頂点 $ u $ から頂点 $ v\ (u,v\in S) $ に辺が張られているとき，その辺を削除し，頂点 $ v $ から頂点 $ u $ への有向辺を追加する．この操作はすべての対象の辺に対して同時に行われる． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

$ \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T $ に対する答えを順に以下の形式で出力せよ． 操作を $ 0 $ 回以上好きな回数行うことで $ G $ を有向閉路を含まないグラフ（DAG）にできるならば `Yes` ，できないならば `No` と出力せよ．

### Sample Explanation 1 $ 1 $ 番目のテストケースでは，以下のように $ 2 $ 回の操作を行うことで $ G $ を有向閉路を含まないグラフにできます． - $ 1 $ 回目の操作では $ S = \lbrace 1, 2,7 \rbrace $ として操作を行う． 始点と終点の番号がともに $ S $ に含まれるような有向辺は頂点 $ 1 $ から頂点 $ 2 $ へ張られた辺と，頂点 $ 7 $ から頂点 $ 1 $ へ張られた辺である．これらの辺の向きが反転する． - $ 2 $ 回目の操作では $ S = \lbrace 4, 5,7 \rbrace $ として操作を行う． 始点と終点の番号がともに $ S $ に含まれるような有向辺は頂点 $ 4 $ から頂点 $ 5 $ へ張られた辺である．この辺の向きが反転し， $ G $ は有向閉路を含まないグラフになる． $ 2 $ 番目のテストケースでは，どのように操作を行っても $ G $ を有向閉路を含まないグラフにできません． ### Constraints - $ 1 \leq T \leq 50000 $ - $ 4 \leq N \leq 2\times 10^5 $ - $ 0 \leq M \leq \min({N(N-1), 2\times 10^5}) $ - $ 2 \leq K \leq N-2 $ - $ 1 \leq a_i, b_i \leq N $ - $ a_i \neq b_i $ - $ i\neq j $ ならば $ (a_i, b_i) \neq (a_j, b_j) $ かつ $ (a_i,b_i) \neq (b_j,a_j) $ - 一つの入力に含まれる $ N $ の総和は $ 2\times 10^5 $ 以下 - 一つの入力に含まれる $ M $ の総和は $ 2\times 10^5 $ 以下 - 入力される数値は全て整数