ハミルトン閉路 (Hamiltonian Cycle)
無向グラフが与えられ、頂点数は
n、辺数は e です。このグラフにハミルトン閉路 (Hamiltonian Cycle) が含まれているかどうかを判定してください。💡
ハミルトン閉路 (Hamiltonian cycle) とは、同じ頂点で始まり同じ頂点で終わり、グラフ中のすべての頂点を一度ずつちょうど訪れる経路を指します。
Input
最初の行には、頂点数を表す整数
n (1 ≤ n ≤ 20) と、辺数を表す整数 e (0 ≤ e ≤ ) が与えられます。続く
e 行には、グラフを構成する辺がそれぞれ記述されています。各行には、頂点 a と b (1 ≤ a, b ≤ n, a ≠ b) が与えられ、これは頂点 a と頂点 b の間に辺があることを示します。Output
グラフにハミルトンパス (Hamiltonian path) またはハミルトン閉路が含まれる場合は
YES と出力し、含まれない場合は NO と出力してください。Examples
入力 | 出力 |
3 3
1 2
2 3
3 1 | YES |
4 4
1 2
2 3
3 1
2 4 | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB