题目详情题解（0）讨论（0）提交记录（0）

AT_nupc2024_m.NUPaCking

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 NN 个顶点、MM 条边的简单无向图 GG。这里，NUPC\mathrm{NUPC} 是如下图所示的图。

黑点表示图的顶点，连接黑点的线段表示图的边。

请你求出可以将 NUPC\mathrm{NUPC} 点素嵌入到 GG 中的最大数量。

也就是说，找出满足以下条件的最大整数 kk：

  • GG 包含 “由 kk 个 NUPC\mathrm{NUPC} 组成的图” 作为子图。

输入格式

输入以以下格式从标准输入中给出。

NN MM u1u_1 v1v_1 u2u_2 v2v_2 ⋯\cdots uMu_M vMv_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

  • 输入#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

  • 输入#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

说明/提示

样例解释 1

该图如上图所示。这个图恰好包含 11 个 NUPC\mathrm{NUPC}。

样例解释 2

该图如上图所示。你可以在某个连通分量中嵌入 22 个 NUPC\mathrm{NUPC}。

数据范围

  • 1≤N,M≤1051 \le N, M \le 10^5
  • 1≤ui,vi≤N1 \leq u_i, v_i \leq N
  • GG 的每个连通分量的顶点数不超过 1010
  • 给定的图是简单图，即不存在自环或重边。
  • 所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页