AT_nupc2024_m NUPaCking

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图 $G$。这里，$\mathrm{NUPC}$ 是如下图所示的图。  黑点表示图的顶点，连接黑点的线段表示图的边。 请你求出可以将 $\mathrm{NUPC}$ 点素嵌入到 $G$ 中的最大数量。 也就是说，找出满足以下条件的最大整数 $k$： - $G$ 包含 “由 $k$ 个 $\mathrm{NUPC}$ 组成的图” 作为子图。

输入以以下格式从标准输入中给出。 > $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\cdots$ $u_M$ $v_M$

请将答案作为一行输出到标准输出。

### 样例解释 1  该图如上图所示。这个图恰好包含 $1$ 个 $\mathrm{NUPC}$。 ### 样例解释 2  该图如上图所示。你可以在某个连通分量中嵌入 $2$ 个 $\mathrm{NUPC}$。 ### 数据范围 - $1 \le N, M \le 10^5$ - $1 \leq u_i, v_i \leq N$ - **$G$ 的每个连通分量的顶点数不超过 $10$** - 给定的图是简单图，即不存在自环或重边。 - 所有输入均为整数。 由 ChatGPT 5 翻译