問題一覧 > 通常問題

No.408 五輪ピック

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 80 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 : 紙ぺーぱー / テスター : btk
ProblemId : 1161 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-13 13:35:45

問題文

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

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

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

入力

N M
A1 B1

AM BM

1 行目に頂点数、及び辺の数を表す 2 つの整数 N,M(2N2×104,0Mmin(N(N1)/2,5×104)) が空白区切りで与えられる。
2 行目から続く M 行の i(1iM) 行目において、 2 つの整数 Ai,Bi(1Ai,BiN) が空白区切りで与えられ、頂点 Ai と頂点 Bi の間に辺があることを示す。
グラフは単純であることが保証される。即ち自己ループや多重辺は存在しない。

出力

答えを 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 つの頂点からなる単純閉路グラフになる。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。