TUNA2026 東京Stage Welcome コンテスト 2026/09/23 14:00 ~ 2026/09/23 18:00 4:00:00

M Detect Induced Diamond

問題
制限時間: 5 sec メモリ制限: 1024 MB
Detect Induced Diamond
Statement

\(N\) 頂点 \(M\) 辺の単純連結無向グラフが与えられます。 頂点には \(1\) から \(N\) までの番号が付けられています。

このグラフが Induced Diamond を含むか判定してください。

Induced Diamond とは、相異なる \(4\) 頂点からなる頂点集合であって、その頂点集合によって誘導される部分グラフがちょうど \(5\) 本の辺を持つものです。 言い換えると、Induced Diamond による誘導部分グラフは、完全グラフ \(K_4\) からちょうど \(1\) 本の辺を取り除いて得られるグラフです。

Input

入力は以下の形式で標準入力から与えられます。

\(N~M\)
\(u_1~v_1\)
\(\vdots\)
\(u_M~v_M\)

制約は以下の通りです。

  • \(2 \leq N \leq 10^5\)
  • \(N-1 \leq M \leq \min\left(2\times 10^5,\frac{N(N-1)}{2}\right)\)
  • \(1 \leq u_i,v_i \leq N\)
  • \(u_i \neq v_i\)
  • 与えられるグラフは単純かつ連結である。
  • 入力はすべて整数である。

Output

グラフが Induced Diamond を含むならば Yes を、含まないならば No を \(1\) 行に出力してください。

Examples

Input 1
4 5
1 2
1 3
1 4
2 3
2 4
Output 1
Yes
Input 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output 2
No
Input 3
5 5
1 2
2 3
3 4
4 5
1 5
Output 3
No
Input 4
5 6
1 2
1 3
2 3
2 4
3 4
4 5
Output 4
Yes

Note

\(1\) 番目のテストケースでは、頂点 \(1,2,3,4\) によって誘導される部分グラフがちょうど \(5\) 本の辺を持つため、これらの頂点は Induced Diamond です。

\(2\) 番目のテストケースは \(K_4\) です。任意の \(4\) 頂点によって誘導される部分グラフは \(6\) 本の辺を持つため、Induced Diamond ではありません。

\(4\) 番目のテストケースでは、頂点 \(1,2,3,4\) が Induced Diamond です。

サンプル