#P2273. [HNOI2002] 交换

    ID: 1285 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选湖南2002概率论统计SplaySBT

[HNOI2002] 交换

题目描述

给定 nn 个整数寄存器 r1,r2,,rnr_1,r_2,\cdots,r_n。我们定义一个比较交换指令 CE(a,b)\text{CE}(a,b) 如下:如果 rar_a 中的值大于 rbr_b 中的值,则交换寄存器 rar_arbr_b 中的值。其中,1a<bn1\leq a<b\leq n

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

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

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

CE(1,2)\text{CE}(1, 2)CE(2,3)\text{CE}(2, 3)CE(1,2)\text{CE}(1, 2)

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

输入格式

共两行,第一行为用空格分开的两个整数 n,mn,m;其中 nn 为寄存器个数(2n1042\leq n\leq 10 ^ 4),mm 为 CE-程序的指令条数(0m200000\leq m\leq20000)。

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

输出格式

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

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

2