神经突击车¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
拉恩被几支敌军围困，神经突击车赶来协助撤离。每辆突击车可以挑起两支敌军之间的冲突，也可以使一支敌军陷入内乱。只要所有敌军都被其中一种方式牵制，撤离就能开始。突击车造价昂贵，请尽量少使用它们。
形式化问题描述¶
有 \(n\) 支军队，以及 \(m\) 对允许制造冲突的军队。一次行动消耗一辆神经突击车，可任选以下一种方式：
- 选择给定的一对军队，使这两支军队都被牵制。
- 选择任意一支军队，使它被内部混乱牵制。
求使全部 \(n\) 支军队都被牵制所需的最少行动次数。允许多次行动涉及同一支军队，但不必这样做。
军队由区分大小写的代号标识，代号只出现在允许制造冲突的关系中。若输入中只出现 \(d<n\) 种代号，其余 \(n-d\) 支军队都没有可用的冲突关系，只能单独制造内部混乱。
输入格式¶
第一行包含两个整数 \(n,m\) .接下来 \(m\) 行，每行两个由空白分隔的代号，表示一对允许制造冲突的军队。
输出格式¶
输出一行一个整数，表示最少行动次数。
样例 1¶
输入¶
8 9
100 200
200 300
300 400
300 500
300 600
400 500
600 500
500 -700
501 -700
输出¶
4
解释¶
可分别选择四对：100–200 、300–600 、400–500 和 501–-700 .每次至多牵制两支军队，所以四次已是最优。
样例 2¶
输入¶
6 6
1 2
2 3
1 3
3 4
4 5
5 6
输出¶
3
解释¶
选择关系 \(1\)–\(2\) 、\(3\)–\(4\) 和 \(5\)–\(6\) ，三次即可覆盖全部军队。
样例 3¶
输入¶
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
输出¶
3
解释¶
选两对互不相交的军队，再使剩下一支军队陷入内部混乱。
样例 4¶
输入¶
3 0
输出¶
3
解释¶
三支军队都没有可用关系，分别处理。
数据范围与保证¶
- \(1\le n\le300\) ，\(0\le m\le n(n-1)/2\) .
- 没有重边或自环；输入中不同代号的数量不超过 \(n\) .
- 每个代号为非空 UTF-8 字符串，长度不超过 \(80\) 字节，只含英文字母、数字、下划线、连字符或汉字；不含空白。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 20% | \(n\le10\) ，\(m\le20\) |
| 20% | 关系图为树或森林 |
| 20% | 每个连通分量恰有一个环 |
| 10% | 关系图为完全图 |
| 30% | 无额外条件 |