시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 10 8 42.105%

문제

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함수 호출 횟수의 최솟값을 출력한다.

예제 입력 1

3 3
1 2 2 3 1 2

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIzNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWFkNTBcdWFkNTBcdWQ2NTgiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHVjMjE4IEFbMV0sIEFbMl0sICZoZWxsaXA7LCBBW25dXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIDEmbGU7YSZsdDtiJmxlO25cdWM3NzggXHViNDUwIFx1YzgxNVx1YzIxOCBhLCBiXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJlNDRcdWFkNTBcdWFkNTBcdWQ2NTgoQ29tcGFyZS1FeGNoYW5nZSkgXHVkNTY4XHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5DRShhLCBiKVxyXG4gICAgaWYoQVthXSAmZ3Q7IEFbYl0pXHJcbiAgICAgICAgU3dhcChBW2FdLCBBW2JdKTs8XC9wcmU+XHJcblxyXG48cD5cdWM5ODksIFx1YjQ1MCBcdWFjMTJcdWM3NDQgXHViZTQ0XHVhZDUwXHVkNTU4XHVjNWVjIFx1YjM1NCBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzc0IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM2MjRcdWIzYzRcdWI4NWQgXHVkNTU4XHViMjk0IFx1ZDU2OFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBDRVx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWIwOThcdWM1ZjRcdWQ1NzQgXHViMTkzXHVjNzQwIFx1YWM4M1x1Yzc0NCBDRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBDRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVkNmM0LCBcdWM1YjRcdWI1YTQgQVsxXSwgQVsyXSwgJmhlbGxpcDssIEFbbl1cdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0IEFbMV1cdWM1ZDAgXHVjZDVjXHVjMTlmXHVhYzEyKEFbMV0sIEFbMl0sICZoZWxsaXA7LCBBW25dIFx1YzkxMVx1YzVkMFx1YzExYylcdWM3NzQgXHVjODAwXHVjN2E1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVhZGY4IENFXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Y2Q1Y1x1YzE4Yy1cdWQwZDBcdWMwYzktQ0VcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkMmI5XHVkNzg4IFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YjRlNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YjBiNFx1Yzc1OCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWNcdWM3NDQgXHVjNzg0XHVjNzU4XHViODVjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWIzYzQgXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4LVx1Y2Q1Y1x1YzE4Yy1cdWQwZDBcdWMwYzktQ0VcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IENFXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzVlY1x1YWUzMFx1YzVkMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YmQ4MFx1YmQ4NFx1YzVkMCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWNcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YzVlYyBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzgtXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBuKDImbGU7biZsZTsxMCwwMDApLCBtKDAmbGU7bSZsZTsyNSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gbVx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgQ0VcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggQ0VcdWQ1NjhcdWMyMTggXHVkNjM4XHVjZDljIFx1ZDY5Zlx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWNcdWM1ZDBcdWMxMWNcdWM3NTggXHViNDUwIFx1Yzc3OFx1Yzc5MCBhLCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1ZDU2MCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWMgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM1NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV4Y2hhbmdlcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gbiBpbnRlZ2VyIHJlZ2lzdGVycyByPHN1Yj4xPFwvc3ViPiwgcjxzdWI+MjxcL3N1Yj4sIC4uLiwgcjxzdWI+bjxcL3N1Yj4gd2UgZGVmaW5lIGEgQ29tcGFyZS1FeGNoYW5nZSBJbnN0cnVjdGlvbiBDRShhLGIpLCB3aGVyZSBhLCBiIGFyZSByZWdpc3RlciBpbmRpY2VzICgxICZsZTsgYSAmbHQ7IGIgJmxlOyBuKTo8XC9wPlxyXG5cclxuPHByZT5cclxuQ0UoYSxiKTo6XHJcbiAgICBpZiBjb250ZW50KHI8c3ViPmE8XC9zdWI+KSAmZ3Q7IGNvbnRlbnQocjxzdWI+YjxcL3N1Yj4pIHRoZW5cclxuICAgICAgICBleGNoYW5nZSB0aGUgY29udGVudHMgb2YgcmVnaXN0ZXJzIHI8c3ViPmE8XC9zdWI+IGFuZCByPHN1Yj5iPFwvc3ViPjtcclxuPFwvcHJlPlxyXG5cclxuPHA+QSBDb21wYXJlLUV4Y2hhbmdlIHByb2dyYW0gKHNob3J0bHkgQ0UtcHJvZ3JhbSkgaXMgYW55IGZpbml0ZSBzZXF1ZW5jZSBvZiBDb21wYXJlLUV4Y2hhbmdlIGluc3RydWN0aW9ucy4gQSBDRS1wcm9ncmFtIGlzIGNhbGxlZCBhIE1pbmltdW0tRmluZGluZyBwcm9ncmFtIGlmIGFmdGVyIGl0cyBleGVjdXRpb24gdGhlIHJlZ2lzdGVyIHI8c3ViPjE8XC9zdWI+IGFsd2F5cyBjb250YWlucyB0aGUgc21hbGxlc3QgdmFsdWUgYW1vbmcgYWxsIHZhbHVlcyBpbiB0aGUgcmVnaXN0ZXJzLiBTdWNoIHByb2dyYW0gaXMgY2FsbGVkIHJlbGlhYmxlIGlmIGl0IHJlbWFpbnMgYSBNaW5pbXVtLUZpbmRpbmcgcHJvZ3JhbSBhZnRlciByZW1vdmluZyBhbnkgc2luZ2xlIENvbXBhcmUtRXhjaGFuZ2UgaW5zdHJ1Y3Rpb24uPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgQ0UtcHJvZ3JhbSBQLCB3aGF0IGlzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgaW5zdHJ1Y3Rpb25zIHRoYXQgc2hvdWxkIGJlIGFkZGVkIGF0IHRoZSBlbmQgb2YgcHJvZ3JhbSBQIGluIG9yZGVyIHRvIGdldCBhIHJlbGlhYmxlIE1pbmltdW0tRmluZGluZyBwcm9ncmFtPzxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIENFLXByb2dyYW0gZm9yIDMgcmVnaXN0ZXJzOjxcL3A+XHJcblxyXG48cD5DRSgxLDIpOyBDRSgyLDMpOyBDRSgxLDIpLjxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBtYWtlIHRoaXMgcHJvZ3JhbSBhIHJlbGlhYmxlIE1pbmltdW0tRmluZGluZyBwcm9ncmFtIGl0IGlzIHN1ZmZpY2llbnQgdG8gYWRkIG9ubHkgdHdvIGluc3RydWN0aW9ucywgQ0UoMSwzKSBhbmQgQ0UoMSwyKS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGZvciBlYWNoIGRhdGEgc2V0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiBhIENFLXByb2dyYW0sPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgQ0UtaW5zdHJ1Y3Rpb25zIHRoYXQgc2hvdWxkIGJlIGFkZGVkIHRvIG1ha2UgdGhpcyBwcm9ncmFtIGEgcmVsaWFibGUgTWluaW11bS1GaW5kaW5nIHByb2dyYW0sPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgZXhhY3RseSBvbmUgcG9zaXRpdmUgaW50ZWdlciBkIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzLCAxICZsZTsgZCAmbGU7IDEwLiBUaGUgZGF0YSBzZXRzIGZvbGxvdy48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBleGFjdGx5IHR3byBjb25zZWN1dGl2ZSBsaW5lcy48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IG9mIHRob3NlIGxpbmVzIGNvbnRhaW5zIGV4YWN0bHkgdHdvIGludGVnZXJzIG4gYW5kIG0gc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCAyICZsZTsgbiAmbGU7IDEwIDAwMCwgMCAmbGU7IG0gJmxlOyAyNSAwMDAuIEludGVnZXIgbiBpcyB0aGUgbnVtYmVyIG9mIHJlZ2lzdGVycyBhbmQgaW50ZWdlciBtIGlzIHRoZSBudW1iZXIgb2YgcHJvZ3JhbSBpbnN0cnVjdGlvbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgb2YgdGhvc2UgbGluZXMgY29udGFpbnMgZXhhY3RseSAybSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyAtIHRoZSBwcm9ncmFtIGl0c2VsZi4gSW50ZWdlcnMgYTxzdWI+ajxcL3N1Yj4sIGI8c3ViPmo8XC9zdWI+IG9uIHBvc2l0aW9uIDJqLTEgYW5kIDJqLCAxICZsZTsgaiAmbGU7IG0sIDEgJmxlOyBhPHN1Yj5qPFwvc3ViPiAmbHQ7IGI8c3ViPmo8XC9zdWI+ICZsZTsgbiwgYXJlIHBhcmFtZXRlcnMgb2YgdGhlIGotdGggaW5zdHJ1Y3Rpb24gaW4gdGhlIHByb2dyYW0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29uc2lzdHMgb2YgZXhhY3RseSBkIGxpbmVzLCBvbmUgbGluZSBmb3IgZWFjaCBkYXRhIHNldC48XC9wPlxyXG5cclxuPHA+TGluZSBpLCAxICZsZTsgaSAmbGU7IGQsIHNob3VsZCBjb250YWluIG9ubHkgb25lIGludGVnZXIgLSB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGluc3RydWN0aW9ucyB0aGF0IHNob3VsZCBiZSBhZGRlZCBhdCB0aGUgZW5kIG9mIHRoZSBpLXRoIGlucHV0IHByb2dyYW0gaW4gb3JkZXIgdG8gbWFrZSB0aGlzIHByb2dyYW0gYSByZWxpYWJsZSBNaW5pbXVtLUZpbmRpbmcgcHJvZ3JhbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=