AT_nupc2024_m NUPaCking

$ N $ 頂点 $ M $ 辺の単純無向グラフ $ G $ が与えられます。ここで、 $ \mathrm{NUPC} $ を以下の図で示すグラフとします。  黒い点はグラフの頂点を、それを結んでいる線分はグラフの辺を表します。 $ G $ に $ \mathrm{NUPC} $ を点素に埋め込むことのできる数の最大値を求めてください。 すなわち、以下を満たす最大の整数 $ k $ を求めてください。 - $ G $ は 「 $ \mathrm{NUPC} $ が $ k $ 個からなるグラフ」を部分グラフとして含む。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

標準出力へ答えを一行で出力してください。

### Sample Explanation 1  グラフは図のようになっています。このグラフは $ \mathrm{NUPC} $ をちょうど $ 1 $ 個含みます。 ### Sample Explanation 2  グラフは図のようになっています。 $ 1 $ つの連結成分に $ 2 $ つの文字を埋め込むこともできます。 ### Constraints - $ 1 \le N, M \le 10^5 $ - $ 1 \leq u_i, v_i \leq N $ - **$ G $ の各連結成分の頂点数は $ 10 $ 以下** - 与えられるグラフは単純である。すなわち、自己ループや多重辺は存在しない。 - 入力はすべて整数