题目描述

译自 CCO 2019 Day2 T2「Marshmallow Molecules」。

哈娜正在为化学课做一个用棉花糖和竹签搭建的结构。这个结构将包含 $N$ 个棉花糖，编号从 $1$ 到 $N$。一些棉花糖会用竹签连接起来，每根竹签连接两个棉花糖。

哈娜对她的结构有 $M$ 个要求。每个要求都用一对数字 $\left(a_{i}, b_{i}\right)$ 表示，这意味着必须有一根竹签连接棉花糖 $a_{i}$ 和棉花糖 $b_{i}$。

为了保证结构的稳定，还必须满足以下要求：如果 $a < b < c$，并且如果一根竹签连接棉花糖 $a$ 和棉花糖 $b$，另一根竹签连接棉花糖 $a$ 和棉花糖 $c$，那么也必须有一根竹签连接棉花糖 $b$ 和棉花糖 $c$。

由于学校校长办公室实施的降本增效政策，竹签在哈娜的学校里很稀缺。请找出满足所有要求的最少竹签数量。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$。

接下来 $M$ 行每行包含两个空格分隔的整数，第 $i$ 行包含 $a_{i}$ 和 $b_{i}$。所有 $M$ 对 $\left(a_{i}, b_{i}\right)$ 都互不相同。

输出格式

输出一个整数，表示最少的总竹签数。

6 4
1 2
1 4
4 6
4 5

6

除了已经要求的之外，还需要在棉花糖编号为 $(2,4)$ 和 $(5,6)$ 的之间添加竹签。

7 6
2 3
2 6
2 7
1 3
1 4
1 5

16

数据范围与提示

对于 $20\%$ 的数据，$N \leq 100$；
对于另外 $20\%$ 的数据，$N \leq 5000$；
对于另外 $20\%$ 的数据，对于所有 $1 \leq j \leq N$，至多存在一对 $\left(a_{i}, b_{i}\right)$ 使得 $b_{i}=j$；
对于 $100\%$ 的数据，$1 \leq N, M \leq 10^{5}$，$1 \leq a_{i}<b_{i} \leq N$。