グラフが効率的かどうかを確認する
無向グラフで頂点数が
v、辺数が e のものが与えられたとき、そのグラフが効率的 (efficient) かどうかを判定してください。ここで「効率的」とは、どの頂点からどの頂点へも最大2本の辺を通るだけで到達できることを意味します。入力
入力の最初の行には、2つの整数
v (1 ≤ v ≤ 100) と e (1 ≤ e ≤ 10 000) が与えられます。続く
e 行には、それぞれ v1, v2 (1 ≤ v1, v2 ≤ v) というペアの整数が記載され、(v1 と v2 の間に) 辺が存在することを表します。出力
もしグラフが効率的であれば
Yes、そうでなければ No を出力してください。例
入力 | 出力 |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
説明
- 頂点 4 は他の頂点とつながっていないため、2本の辺まででは頂点 4 から他の頂点へ移動できません。
- どの頂点からでも、2本の辺を通るだけで他の頂点に到達できます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB