Reliable MIN‐Program Augmentation

We have n registers \(r_1,r_2,\dots,r_n\) holding integer values. A compare‐exchange (CE) instruction \(\mathrm{CE}(a,b)\) with \(1 \le a r_b\) then the values in \(r_a\) and \(r_b\) are swapped; otherwise nothing happens. A CE–program is a finite sequence of such instructions. A program is called a MIN–program if after its execution the value in \(r_1\) is the minimum among all registers. Furthermore, if after removing any one instruction the program still is a MIN–program then it is said to be a reliable MIN–program.

You are given a CE–program \(P\) which is a MIN–program but may not be reliable. Your task is to compute the minimum number of extra instructions that have to be appended to the end of \(P\) in order to make it a reliable MIN–program.

Observation: In order for the overall program to be reliable, each register \(r_j\) for \(j=2,3,\dots,n\) must have a "backup" way of bringing its value to \(r_1\) when any one instruction is removed. A simple sufficient condition is to ensure that for each \(j\ge2\) there are at least two CE instructions in the entire program (original plus appended) of the form \(\mathrm{CE}(1,j)\). (In any execution these instructions directly compare \(r_1\) with \(r_j\); if one of them is missing due to a fault the other can still bring a smaller value into \(r_1\) if needed.)

Since the input program \(P\) is guaranteed to be a MIN–program, every register \(r_j\) (with \(j\ge2\)) is eventually connected to \(r_1\) (possibly indirectly). However, if there is only one direct instruction of the form \(\mathrm{CE}(1,j)\) in \(P\) then if that instruction fails the outcome might be wrong. Thus, for each \(j = 2,3,\dots,n\) we require at least two occurrences of instructions of the form
\(\mathrm{CE}(1,j)\)

Your task is to count, for every register \(j\ge2\), the number of occurrences of \(\mathrm{CE}(1,j)\) in the given program, and then to determine the extra copies needed so that every such register has two direct instructions. In other words, if register \(r_j\) appears with \(c_j\) direct instructions in \(P\), you must append \(\max(0,2-c_j)\) extra instructions \(\mathrm{CE}(1,j)\). The answer is the sum over all registers \(j=2,3,\dots, n\).

Example: Consider the program with three registers \[ \mathrm{CE}(1,2),\; \mathrm{CE}(2,3),\; \mathrm{CE}(1,2). \] For register \(r_2\), there are already two instructions \(\mathrm{CE}(1,2)\); however, for \(r_3\) there are none. Hence, we need to append \(\max(0,2-0)=2\) extra instructions (namely, two copies of \(\mathrm{CE}(1,3)\)) so that every register has at least two direct comparisons with \(r_1\). One acceptable appended sequence is: \(\mathrm{CE}(1,3)\) and then \(\mathrm{CE}(1,3)\). (Note that the sample output below is 2.)

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(n \ge 2\)) representing the number of registers and the number of instructions in the program, respectively. Each of the following \(m\) lines contains two integers \(a\) and \(b\) (with \(1 \le a < b \le n\)), representing the instruction \(\mathrm{CE}(a,b)\).

outputFormat

Output a single integer, the minimum number of extra instructions that need to be appended to the original program to make it a reliable MIN–program.

sample

3 3
1 2
2 3
1 2

2