비교 교환

n개의 수 A[1], A[2], ..., A[n]이 있다. 두 정수 a, b (1 <= a < b <= n)에 대해 비교 교환 함수 CE(a, b)는 다음과 같이 정의된다.

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

CE(a, b)는 두 값을 비교해 더 작은 값이 앞쪽 인덱스 a에 오도록 한다.

CE 함수 호출들을 순서대로 나열한 것을 CE 프로그램이라고 하자. 어떤 CE 프로그램을 실행한 뒤, 어떤 초기 배열 A에 대해서도 A[1]에 전체 최솟값이 저장된다면 그 프로그램은 최소 탐색 CE 프로그램이다.

또한 프로그램 안의 CE 함수 호출 중 임의의 하나를 제거해도 여전히 최소 탐색 CE 프로그램이라면, 그 프로그램은 안정적인 최소 탐색 CE 프로그램이다.

주어진 CE 프로그램의 끝에 CE 함수 호출을 몇 개 추가하여 안정적인 최소 탐색 CE 프로그램으로 만들려고 한다. 추가해야 하는 CE 함수 호출 횟수의 최솟값을 구하라.

첫째 줄에 두 정수 n (2 <= n <= 10,000), m (0 <= m <= 25,000)이 주어진다. m은 주어진 CE 프로그램에 포함된 CE 함수 호출 횟수이다.

다음 줄에는 2m개의 정수가 주어진다. 이 수들은 두 개씩 순서대로 묶어 각 CE 함수 호출의 인자 a, b를 나타낸다.

추가해야 하는 CE 함수 호출 횟수의 최솟값을 첫째 줄에 출력한다.