题目描述

给定 $n$ 个整数寄存器 $r_1,r_2,\cdots,r_n$。我们定义一个比较交换指令 $\text{CE}(a,b)$ 如下：如果 $r_a$ 中的值大于 $r_b$ 中的值，则交换寄存器 $r_a$ 和 $r_b$ 中的值。其中，$1\leq a<b\leq n$。

一个比较交换程序（简称为 CE-程序）就是一个有限交换指令序列。称一个 CE-程序为 MIN-程序，如果在该程序执行之后，寄存器 $r_1$ 中的值是所有寄存器中的值的最小者；如果一个 CE-程序在删除其中任意一条交换指令后，仍然是一个 MIN-程序，则称该 CE-程序是可靠的 MIN-程序。

你的任务是：给定一个 CE-程序 P，编程求出至少在程序 P 的尾部增加多少条指令才能使程序 P 成为可靠的 MIN-程序。

例如，考虑下列三个寄存器的 CE-程序：

$\text{CE}(1, 2)$，$\text{CE}(2, 3)$，$\text{CE}(1, 2)$。

我们仅需要增加两条指令：$\text{CE}(1, 3)$，$\text{CE}(1, 2)$ 就可使该 CE-程序成为可靠的 MIN-程序。

输入格式

共两行，第一行为用空格分开的两个整数 $n,m$；其中 $n$ 为寄存器个数（$2\leq n\leq 10 ^ 4$），$m$ 为 CE-程序的指令条数（$0\leq m\leq20000$）。

接下来为 $m$ 条指令 $\text{CE}(a,b)$，$a,b$ 之间用逗号分隔，两条指令之间也用逗号分隔。

输出格式

共一行一个整数即应该增加的最少指令条数。

3 3
1,2,2,3,1,2

2