← 返回题目列表

AtCoder · nupc2024_m

M. NUPaC 打包

中文机器翻译题面 查看原题

配点 : 100 点

問題文

N 頂点 M 边的简单无向图 G 。在这里, \mathrm{NUPC} 用以下图表示的图。

黑点表示图的顶点,连接它们的线段表示图的边。

G 中,加上 \mathrm{NUPC} 求能够嵌入点素的最大数量。

也就是说,满足以下条件的最大整数 k 。

  • G 是「 \mathrm{NUPC} 是 k 个顶点组成的图」作为子图包含的数量。

制約

  • 1 \le N, M \le 10^5
  • 1 \leq u_i, v_i \leq N
  • G 的每个连通分支的顶点数是 10 以下
  • 给出的涂鸦很简单。 换句话说,不存在自环或平衡边。
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

请将你的答案以一行方式输出到标准输出。


入力例 1

23 20
1 2
2 3
3 4
4 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
14 15
15 16
14 17
17 18
18 15
19 20
20 21
21 22
22 23

出力例 1

1

图形如图所示。 这张刻画 \mathrm{NUPC} 刚好 1 包含一个。


入力例 2

23 21
1 2
2 3
3 4
4 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
14 15
15 16
14 17
17 18
18 15
19 20
20 21
21 22
22 23
14 21

出力例 2

1

图形如图所示。 1 以连接组件 你还可以嵌入 2 角色。


入力例 3

49 60
40 25
40 43
40 31
40 21
7 21
3 25
3 31
3 21
25 43
25 49
21 49
21 39
49 26
39 26
38 8
38 17
41 22
41 8
41 15
22 8
22 15
22 30
8 30
5 15
5 11
15 11
48 11
12 13
29 1
29 44
28 1
28 36
13 10
13 16
13 44
10 36
1 36
36 44
45 32
45 35
32 14
14 33
14 35
33 4
35 4
20 37
20 47
37 9
18 27
18 47
18 23
46 23
46 9
23 9
24 2
24 19
2 34
6 34
6 42
34 42

出力例 3

2