No.408 五輪ピック

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 80 MB / 通常問題
タグ : / 解いたユーザー数 61
作問者 : 紙ぺーぱー紙ぺーぱー / テスター : btkbtk

8 ProblemId : 1161 / 出題時の順位表

問題文

$N$ 頂点、 $M$ 本の無向辺からなる単純無向グラフがあり、各頂点には $1$ から $N$ の番号がついている。
このグラフに頂点 $1$ を含む長さ $5$ の単純閉路が存在するならば$\verb|"YES"|$を、そうでなければ$\verb|"NO"|$を出力せよ。

無向グラフに以下を満たす頂点集合 $(a,b,c,d,e)$ が存在するとき、長さ $5$ の単純閉路が存在するという。

  • $a,b,c,d,e$ は互いに相異なる
  • 頂点 $a,b$ は隣接する
  • 頂点 $b,c$ は隣接する
  • 頂点 $c,d$ は隣接する
  • 頂点 $d,e$ は隣接する
  • 頂点 $e,a$ は隣接する

入力

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

$1$ 行目に頂点数、及び辺の数を表す $2$ つの整数 $N,\;M(2 \leq N \leq 2 \times 10^{4},\; 0 \leq M \leq \text{min}(N(N-1)/2,\;5 \times 10^{4}))$ が空白区切りで与えられる。
$2$ 行目から続く $M$ 行の $i(1 \leq i \leq M)$ 行目において、 $2$ つの整数 $A_i, B_i (1\leq A_i, B_i \leq N)$ が空白区切りで与えられ、頂点 $A_i$ と頂点 $B_i$ の間に辺があることを示す。
グラフは単純であることが保証される。即ち自己ループや多重辺は存在しない。

出力

答えを $1$ 行で出力せよ。

サンプル

サンプル1
入力
5 5
1 2
2 3
3 4
4 5
5 1
出力
YES

このグラフは $5$ つの頂点からなる単純閉路グラフそのものである。

サンプル2
入力
5 4
1 2
2 3
3 4
4 5
出力
NO

閉路が存在しない。

サンプル3
入力
6 6
1 2
2 3
3 4
4 5
5 6
6 2
出力
NO

頂点 $1$ を含むものはない。

サンプル4
入力
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
出力
YES

適当に辺を取り除くと $5$ つの頂点からなる単純閉路グラフになる。

サンプル5
入力
7 10
1 2
1 3
1 4
1 5
2 3
2 4
2 6
3 4
3 7
4 5
出力
YES

適当に頂点と辺を取り除くと $5$ つの頂点からなる単純閉路グラフになる。

提出ページヘ