시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB25131150.000%

문제

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함수 호출 횟수이다. 다음 줄에는 2m개의 정수가 주어진다. 2개씩 순서대로 CE함수 호출에서의 두 인자 a, b이다.

출력

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

예제 입력 1

3 3
1 2 2 3 1 2

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIzNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWFkNTBcdWFkNTBcdWQ2NTgiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHVjMjE4IEFbMV0sIEFbMl0sICZoZWxsaXA7LCBBW25dXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIDEgJmxlOyBhICZsdDsgYiAmbGU7IG5cdWM3NzggXHViNDUwIFx1YzgxNVx1YzIxOCBhLCBiXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJlNDRcdWFkNTBcdWFkNTBcdWQ2NTgoQ29tcGFyZS1FeGNoYW5nZSkgXHVkNTY4XHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5DRShhLCBiKVxyXG4gICAgaWYoQVthXSAmZ3Q7IEFbYl0pXHJcbiAgICAgICAgU3dhcChBW2FdLCBBW2JdKTs8XC9wcmU+XHJcblxyXG48cD5cdWM5ODksIFx1YjQ1MCBcdWFjMTJcdWM3NDQgXHViZTQ0XHVhZDUwXHVkNTU4XHVjNWVjIFx1YjM1NCBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzc0IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM2MjRcdWIzYzRcdWI4NWQgXHVkNTU4XHViMjk0IFx1ZDU2OFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBDRVx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWIwOThcdWM1ZjRcdWQ1NzQgXHViMTkzXHVjNzQwIFx1YWM4M1x1Yzc0NCBDRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBDRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVkNmM0LCBcdWM1YjRcdWI1YTQgQVsxXSwgQVsyXSwgJmhlbGxpcDssIEFbbl1cdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0IEFbMV1cdWM1ZDAgXHVjZDVjXHVjMTlmXHVhYzEyKEFbMV0sIEFbMl0sICZoZWxsaXA7LCBBW25dIFx1YzkxMVx1YzVkMFx1YzExYylcdWM3NzQgXHVjODAwXHVjN2E1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVhZGY4IENFXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Y2Q1Y1x1YzE4Yy1cdWQwZDBcdWMwYzktQ0VcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkMmI5XHVkNzg4IFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YjRlNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YjBiNFx1Yzc1OCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWNcdWM3NDQgXHVjNzg0XHVjNzU4XHViODVjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWIzYzQgXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4LVx1Y2Q1Y1x1YzE4Yy1cdWQwZDBcdWMwYzktQ0VcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IENFXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzVlY1x1YWUzMFx1YzVkMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YmQ4MFx1YmQ4NFx1YzVkMCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWNcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YzVlYyBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzgtXHVjZDVjXHVjMThjLVx1ZDBkMFx1YzBjOS1DRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBuKDIgJmxlOyBuICZsZTsgMTAsMDAwKSwgbSgwICZsZTsgbSAmbGU7IDI1LDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBtXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBDRVx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBDRVx1ZDU2OFx1YzIxOCBcdWQ2MzhcdWNkOWMgXHVkNjlmXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IDJtXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDJcdWFjMWNcdWM1MjkgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIENFXHVkNTY4XHVjMjE4IFx1ZDYzOFx1Y2Q5Y1x1YzVkMFx1YzExY1x1Yzc1OCBcdWI0NTAgXHVjNzc4XHVjNzkwIGEsIGJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NjAgQ0VcdWQ1NjhcdWMyMTggXHVkNjM4XHVjZDljIFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzNTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFeGNoYW5nZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIG4gaW50ZWdlciByZWdpc3RlcnMgcjxzdWI+MTxcL3N1Yj4sIHI8c3ViPjI8XC9zdWI+LCAuLi4sIHI8c3ViPm48XC9zdWI+IHdlIGRlZmluZSBhIENvbXBhcmUtRXhjaGFuZ2UgSW5zdHJ1Y3Rpb24gQ0UoYSxiKSwgd2hlcmUgYSwgYiBhcmUgcmVnaXN0ZXIgaW5kaWNlcyAoMSAmbGU7IGEgJmx0OyBiICZsZTsgbik6PFwvcD5cclxuXHJcbjxwcmU+XHJcbkNFKGEsYik6OlxyXG4gICAgaWYgY29udGVudChyPHN1Yj5hPFwvc3ViPikgJmd0OyBjb250ZW50KHI8c3ViPmI8XC9zdWI+KSB0aGVuXHJcbiAgICAgICAgZXhjaGFuZ2UgdGhlIGNvbnRlbnRzIG9mIHJlZ2lzdGVycyByPHN1Yj5hPFwvc3ViPiBhbmQgcjxzdWI+YjxcL3N1Yj47XHJcbjxcL3ByZT5cclxuXHJcbjxwPkEgQ29tcGFyZS1FeGNoYW5nZSBwcm9ncmFtIChzaG9ydGx5IENFLXByb2dyYW0pIGlzIGFueSBmaW5pdGUgc2VxdWVuY2Ugb2YgQ29tcGFyZS1FeGNoYW5nZSBpbnN0cnVjdGlvbnMuIEEgQ0UtcHJvZ3JhbSBpcyBjYWxsZWQgYSBNaW5pbXVtLUZpbmRpbmcgcHJvZ3JhbSBpZiBhZnRlciBpdHMgZXhlY3V0aW9uIHRoZSByZWdpc3RlciByPHN1Yj4xPFwvc3ViPiBhbHdheXMgY29udGFpbnMgdGhlIHNtYWxsZXN0IHZhbHVlIGFtb25nIGFsbCB2YWx1ZXMgaW4gdGhlIHJlZ2lzdGVycy4gU3VjaCBwcm9ncmFtIGlzIGNhbGxlZCByZWxpYWJsZSBpZiBpdCByZW1haW5zIGEgTWluaW11bS1GaW5kaW5nIHByb2dyYW0gYWZ0ZXIgcmVtb3ZpbmcgYW55IHNpbmdsZSBDb21wYXJlLUV4Y2hhbmdlIGluc3RydWN0aW9uLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIENFLXByb2dyYW0gUCwgd2hhdCBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGluc3RydWN0aW9ucyB0aGF0IHNob3VsZCBiZSBhZGRlZCBhdCB0aGUgZW5kIG9mIHByb2dyYW0gUCBpbiBvcmRlciB0byBnZXQgYSByZWxpYWJsZSBNaW5pbXVtLUZpbmRpbmcgcHJvZ3JhbT88XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBDRS1wcm9ncmFtIGZvciAzIHJlZ2lzdGVyczo8XC9wPlxyXG5cclxuPHA+Q0UoMSwyKTsgQ0UoMiwzKTsgQ0UoMSwyKS48XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8gbWFrZSB0aGlzIHByb2dyYW0gYSByZWxpYWJsZSBNaW5pbXVtLUZpbmRpbmcgcHJvZ3JhbSBpdCBpcyBzdWZmaWNpZW50IHRvIGFkZCBvbmx5IHR3byBpbnN0cnVjdGlvbnMsIENFKDEsMykgYW5kIENFKDEsMikuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBmb3IgZWFjaCBkYXRhIHNldDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgZGVzY3JpcHRpb24gb2YgYSBDRS1wcm9ncmFtLDxcL2xpPlxyXG5cdDxsaT5jb21wdXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIENFLWluc3RydWN0aW9ucyB0aGF0IHNob3VsZCBiZSBhZGRlZCB0byBtYWtlIHRoaXMgcHJvZ3JhbSBhIHJlbGlhYmxlIE1pbmltdW0tRmluZGluZyBwcm9ncmFtLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGV4YWN0bHkgb25lIHBvc2l0aXZlIGludGVnZXIgZCBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cywgMSAmbGU7IGQgJmxlOyAxMC4gVGhlIGRhdGEgc2V0cyBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgZXhhY3RseSB0d28gY29uc2VjdXRpdmUgbGluZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBvZiB0aG9zZSBsaW5lcyBjb250YWlucyBleGFjdGx5IHR3byBpbnRlZ2VycyBuIGFuZCBtIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgMiAmbGU7IG4gJmxlOyAxMCAwMDAsIDAgJmxlOyBtICZsZTsgMjUgMDAwLiBJbnRlZ2VyIG4gaXMgdGhlIG51bWJlciBvZiByZWdpc3RlcnMgYW5kIGludGVnZXIgbSBpcyB0aGUgbnVtYmVyIG9mIHByb2dyYW0gaW5zdHJ1Y3Rpb25zLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIG9mIHRob3NlIGxpbmVzIGNvbnRhaW5zIGV4YWN0bHkgMm0gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgLSB0aGUgcHJvZ3JhbSBpdHNlbGYuIEludGVnZXJzIGE8c3ViPmo8XC9zdWI+LCBiPHN1Yj5qPFwvc3ViPiBvbiBwb3NpdGlvbiAyai0xIGFuZCAyaiwgMSAmbGU7IGogJmxlOyBtLCAxICZsZTsgYTxzdWI+ajxcL3N1Yj4gJmx0OyBiPHN1Yj5qPFwvc3ViPiAmbGU7IG4sIGFyZSBwYXJhbWV0ZXJzIG9mIHRoZSBqLXRoIGluc3RydWN0aW9uIGluIHRoZSBwcm9ncmFtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3RzIG9mIGV4YWN0bHkgZCBsaW5lcywgb25lIGxpbmUgZm9yIGVhY2ggZGF0YSBzZXQuPFwvcD5cclxuXHJcbjxwPkxpbmUgaSwgMSAmbGU7IGkgJmxlOyBkLCBzaG91bGQgY29udGFpbiBvbmx5IG9uZSBpbnRlZ2VyIC0gdGhlIHNtYWxsZXN0IG51bWJlciBvZiBpbnN0cnVjdGlvbnMgdGhhdCBzaG91bGQgYmUgYWRkZWQgYXQgdGhlIGVuZCBvZiB0aGUgaS10aCBpbnB1dCBwcm9ncmFtIGluIG9yZGVyIHRvIG1ha2UgdGhpcyBwcm9ncmFtIGEgcmVsaWFibGUgTWluaW11bS1GaW5kaW5nIHByb2dyYW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Central European Regional Contest > CERC 2001 E번