Compare Exchange

There are n numbers A[1], A[2], ..., A[n]. For two integers a and b (1 <= a < b <= n), the compare-exchange function CE(a, b) is defined as follows.

CE(a, b)    if (A[a] > A[b])        Swap(A[a], A[b]);

CE(a, b) compares the two values and places the smaller value at the earlier index a.

A sequence of CE function calls is called a CE program. If, after running a CE program, A[1] contains the minimum value among all A[1], A[2], ..., A[n] for every possible initial array A, then the program is a minimum-finding CE program.

If the program is still a minimum-finding CE program after removing any one CE function call from it, then it is a stable minimum-finding CE program.

Given a CE program, append as few CE function calls as possible to the end so that the resulting program becomes a stable minimum-finding CE program. Find the minimum number of CE function calls that must be added.

The first line contains two integers n (2 <= n <= 10,000) and m (0 <= m <= 25,000). Here, m is the number of CE function calls in the given CE program.

The next line contains 2m integers. Reading them two at a time in order gives the two arguments a and b of each CE function call.

Print the minimum number of CE function calls that must be added.