グラフがクラウンであるかを判定する
無向グラフが与えられ、頂点数が
v、辺の数が e となっています。このとき、そのグラフが「クラウングラフ」であるかどうかを判定してください。クラウングラフは「ベース」と呼ばれる部分と、任意の本数の「スパイク」から構成されます。ベースは2つのノードを結ぶ1本の辺で、全スパイクがこの共通の辺につながっています。各スパイクは、ベースの両端をもつ辺に対して、ちょうど1つのノードが両方の頂点と接続される形をとります。
入力
入力の最初の行には
v (1 ≤ v ≤ 1000) と e (1 ≤ e ≤ 10 000) の2つの整数が与えられます。続く
e 行には、各行に v1、v2 (1 ≤ v1, v2 ≤ v) という2つの整数が書かれており、これは v1 と v2 を結ぶ辺を表します。出力
グラフがクラウングラフであると判定できる場合は "Yes" を、そうでない場合は "No" を出力してください。
例
入力 | 出力 |
4 4
1 2
2 3
3 1
1 4 | No |
7 11
3 4
2 3
2 4
1 3
1 4
7 3
7 4
6 3
6 4
5 3
5 4 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB