题目描述

给定n个整数寄存器 。我们定义一个比较交换指令CE（a,b）如下：

CE（a,b）：

  IF   THEN 交换寄存器 

（其中，1≦a<b≦n）

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

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

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

CE（1，2），CE（2，3），CE（1，2）。

我们仅需要增加2条指令：CE（1，3），CE（1，2）；就可使该CE-程序成为可靠的MIN-程序。

输入格式

共2行，第1行为用空格分开的2个整数n,m;其中n为寄存器个数（2≦n≦10000），m为CE-程序的指令条数（0≦m≦2500）。

接下来为m条指令CE（a,b），a,b之间用逗号分隔，两条指令之间也用逗号分隔。

输出格式

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

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

2