
ZOJ Problem Set  1388
Given n integer registers r1, r2, ..., rn we define a CompareExchange Instruction CE(a, b), where a, b are register indices (1 <= a < b <= n): CE(a, b):: A CompareExchange program (shortly CEprogram) is any nite sequence of CompareExchange instructions. A CEprogram is called a MinimumFinding program if after its execution the register r1 always contains the smallest value among all values in the registers. Such program is called reliable if it remains a MinimumFinding program after removing any single CompareExchange instruction. Given a CEprogram P , what is the smallest number of instructions that should be added at the end of program P in order to get a reliable MinimumFinding program?
CE(1, 2); CE(2, 3); CE(1, 2).
reads the description of a CEprogram, computes the smallest number of CEinstructions that should be added to make this program a reliable MinimumFinding program, writes the result.
Each data set consists of exactly two consecutive lines. The first of those lines contains exactly two integers n and m separated by a single space, 2 <= n <= 10 000, 0 <= m <= 25 000. Integer n is the number of registers and integer m is the number of program instructions. The second of those lines contains exactly 2m integers separated by single
spaces  the program
Line i, 1 <= i <= d, should contain only one integer  the smallest number of instructions that should be added at the end of the ith input program in order to make this program a reliable MinimumFinding program.
Source: Central Europe 2001 