Hannah 正在为她的化学课制作一个由棉花糖和烤肉签组成的结构。该结构将包含 $N$ 个棉花糖，编号从 $1$ 到 $N$。一些棉花糖之间会用烤肉签连接。每根烤肉签连接两个棉花糖。

Hannah 对她的结构有 $M$ 个要求。每个要求由一对 $(a_i, b_i)$ 给出，这意味着必须有一根烤肉签连接棉花糖 $a_i$ 和棉花糖 $b_i$。

为了确保结构的稳定性，还必须满足以下要求：如果 $a < b < c$，且存在一根连接棉花糖 $a$ 和 $b$ 的烤肉签，同时也存在一根连接棉花糖 $a$ 和 $c$ 的烤肉签，那么也必须存在一根连接棉花糖 $b$ 和 $c$ 的烤肉签。

由于校长办公室实施的紧缩措施，Hannah 学校里的烤肉签非常稀缺。请找出满足所有要求所需的最少烤肉签数量。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$ ($1 \le N, M \le 10^5$)。

接下来的 $M$ 行，每行包含两个空格分隔的整数，其中第 $i$ 行包含 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le N$)。所有 $M$ 对 $(a_i, b_i)$ 均不相同。

在总分 25 分中，有 5 分满足 $N \le 100$。

在总分 25 分中，另有 5 分满足 $N \le 5000$。

在总分 25 分中，另有 5 分满足对于所有 $1 \le j \le N$，至多存在一对 $(a_i, b_i)$ 使得 $b_i = j$。

输出格式

输出一个整数，即所需的最少烤肉签总数。

样例

输入 1

6 4
1 2
1 4
4 6
4 5

输出 1

6

说明 1

除了已经要求的那些烤肉签外，在棉花糖对 $(2, 4)$ 和 $(5, 6)$ 之间也必须有烤肉签。

输入 2

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

输出 2

16