P2273 [HNOI2002] Swap

Given $n$ integer registers $r_1, r_2, \cdots, r_n$. We define a compare-exchange instruction $\text{CE}(a,b)$ as follows: if the value in $r_a$ is greater than the value in $r_b$, then swap the values in registers $r_a$ and $r_b$. Here, $1 \leq a < b \leq n$. A compare-exchange program (abbreviated as a CE program) is a finite sequence of compare-exchange instructions. A CE program is called a MIN program if, after executing the program, the value in register $r_1$ is the minimum among all registers. If a CE program remains a MIN program after removing any single instruction from it, then the CE program is called a reliable MIN program. Your task is: given a CE program $P$, compute the minimum number of instructions that must be appended to the end of $P$ to make $P$ a reliable MIN program. For example, consider the following CE program on three registers: $\text{CE}(1, 2)$, $\text{CE}(2, 3)$, $\text{CE}(1, 2)$. We only need to append two instructions: $\text{CE}(1, 3)$, $\text{CE}(1, 2)$ to make this CE program a reliable MIN program.

There are two lines. The first line contains two space-separated integers $n$ and $m$; here $n$ is the number of registers ($2 \leq n \leq 10 ^ 4$), and $m$ is the number of instructions in the CE program ($0 \leq m \leq 20000$). The second line contains $m$ instructions $\text{CE}(a, b)$. Inside each instruction, $a$ and $b$ are separated by a comma, and different instructions are also separated by commas.

Output a single integer on one line: the minimal number of instructions that should be appended.

Translated by ChatGPT 5