시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 7 5 55.556%

문제

n개의 수 A[1], A[2], …, A[n]이 있을 때, 1≤a<b≤n인 두 정수 a, b에 대해서 비교교환(Compare-Exchange) 함수는 다음과 같이 정의된다.

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

즉, 두 값을 비교하여 더 작은 값이 앞으로 오도록 하는 함수이다. 이와 같은 CE함수를 나열해 놓은 것을 CE프로그램이라 한다. 어떤 CE프로그램을 수행한 후, 어떤 A[1], A[2], …, A[n]에 대해서도 A[1]에 최소값(A[1], A[2], …, A[n] 중에서)이 저장될 경우, 그 CE프로그램을 최소-탐색-CE프로그램 이라고 한다. 특히 이와 같은 최소-탐색-CE프로그램들 중에서 프로그램 내의 CE함수 호출을 임의로 하나 제거해도 최소-탐색-CE프로그램인 것을 안정적인-최소-탐색-CE프로그램 이라고 한다.

어떤 CE프로그램이 주어졌을 때, 여기에 CE함수 호출을 최소로 추가하여 안정적인-최소-탐색-CE프로그램이 되도록 하려 한다.

입력

첫째 줄에 두 정수 n(2≤n≤10,000), m(0≤m≤25,000)이 주어진다. m은 주어진 CE프로그램의 CE함수 호출 횟수이다. 다음 m개의 줄에는 순서대로 CE함수 호출에서의 두 인자 a, b가 주어진다.

출력

첫째 줄에 추가할 CE함수 호출 횟수의 최소값을 출력한다.

예제 입력

3 3
1 2 2 3 1 2

예제 출력

2

힌트