# 神经突击车

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

拉恩被几支敌军围困，神经突击车赶来协助撤离。每辆突击车可以挑起两支敌军之间的冲突，也可以使一支敌军陷入内乱。只要所有敌军都被其中一种方式牵制，撤离就能开始。突击车造价昂贵，请尽量少使用它们。

## 形式化问题描述

有 $n$ 支军队，以及 $m$ 对允许制造冲突的军队。一次行动消耗一辆神经突击车，可任选以下一种方式：

- 选择给定的一对军队，使这两支军队都被牵制。
- 选择任意一支军队，使它被内部混乱牵制。

求使全部 $n$ 支军队都被牵制所需的最少行动次数。允许多次行动涉及同一支军队，但不必这样做。

军队由区分大小写的代号标识，代号只出现在允许制造冲突的关系中。若输入中只出现 $d<n$ 种代号，其余 $n-d$ 支军队都没有可用的冲突关系，只能单独制造内部混乱。

## 输入格式

第一行包含两个整数 $n,m$ .接下来 $m$ 行，每行两个由空白分隔的代号，表示一对允许制造冲突的军队。

## 输出格式

输出一行一个整数，表示最少行动次数。

## 样例 1

### 输入

```text
8 9
100 200
200 300
300 400
300 500
300 600
400 500
600 500
500 -700
501 -700
```

### 输出

```text
4
```

### 解释

可分别选择四对：`100–200` 、`300–600` 、`400–500` 和 `501–-700` .每次至多牵制两支军队，所以四次已是最优。

## 样例 2

### 输入

```text
6 6
1 2
2 3
1 3
3 4
4 5
5 6
```

### 输出

```text
3
```

### 解释

选择关系 $1$–$2$ 、$3$–$4$ 和 $5$–$6$ ，三次即可覆盖全部军队。

## 样例 3

### 输入

```text
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
```

### 输出

```text
3
```

### 解释

选两对互不相交的军队，再使剩下一支军队陷入内部混乱。

## 样例 4

### 输入

```text
3 0
```

### 输出

```text
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% | 无额外条件 |