グラフはクリークの集合で構成されているか？
クリーク (clique) とは、無向グラフにおける頂点の部分集合のうち、その中の任意の異なる頂点同士がすべて辺で結ばれているものを指します。言い換えると、すべての頂点がお互いに接続された完全部分グラフをクリークと呼びます。
頂点数
v と辺数 e をもつ無向グラフが与えられたときに、このグラフが互いに交わらないクリークの集まりになっているかどうかを判定してください。入力
最初の行には、整数
v (1 ≤ v ≤ 1000) と e (1 ≤ e ≤ ) が与えられます。続く
e 行には、2 つの整数 v1, v2 (1 ≤ v1, v2 ≤ v) が与えられます。これは、頂点 v1 と頂点 v2 が相互に接続されていることを表します。出力
もし与えられたグラフが互いに交わらないクリークの集合であれば
Yes、そうでなければ No を出力してください。例
入力 | 出力 |
3 3
1 2
2 3
1 3 | Yes |
5 4
1 2
2 3
1 3
4 5 | Yes |
5 5
1 2
2 3
1 3
3 4
4 5 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB