AT_agc067_a [AGC067A] Big Clique Everywhere

[problemUrl]: https://atcoder.jp/contests/agc067/tasks/agc067_a $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の単純無向グラフ $ G $ が与えられます。 $ G $ は $ M $ 本の辺を持ち、$ i $ 本目の辺は頂点 $ A_i $ と $ B_i $ を結びます。 $ G $ が次の条件を満たすか判定してください。 - 頂点集合 $ \{1,2,\cdots,N\} $ のすべての部分集合 $ X $ に対して、$ X $ の部分集合 $ Y $ であって $ |Y|\ge\ \frac{|X|}{2} $ かつ $ Y $ がクリークを形成するものが存在する。 解くべきテストケースは $ T $ 個あります。

入力は標準入力から以下の形式で与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

各テストケースについて、$ G $ が条件を満たすなら `Yes`、そうでないなら `No` と出力せよ。 `Yes` または `No` の出力において、各文字は大文字・小文字のいずれでもよい。

### 制約 - $ 1\le\ T\ \le\ 10^3 $ - $ 1\le\ N\ \le\ 10^5 $ - $ 0\ \le\ M\ \le\ 10^6 $ - $ 1\ \le\ A_i,B_i\ \le\ N $ - 与えられるグラフは自己辺も多重辺も含まない。 - ひとつの入力の中のテストケースすべてにわたる $ N $ の総和は $ 10^5 $ 以下である。 - ひとつの入力の中のテストケースすべてにわたる $ M $ の総和は $ 10^6 $ 以下である。 - すべての入力値は整数である。 ### Sample Explanation 1 $ 1 $ 番目のテストケースについて、$ G $ は条件を満たします。 この場合、すべての部分集合 $ X $ がクリークであるため、単に $ Y=X $ とできます。 $ 2 $ 番目のテストケースについて、$ G $ は条件を満たします。 例えば、$ X=\{2,3\} $ に対しては、$ Y=\{2\} $ とできます。 $ 4 $ 番目のテストケースについて、$ G $ は条件を満たしません。 $ X=\{1,2,3\} $ とすると、条件を満たす $ X $ の部分集合 $ Y $ はありません。