시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB284615232327619.412%

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다. 

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

예제 입력 1

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

예제 출력 1

5
-1
6
W3sicHJvYmxlbV9pZCI6IjU3MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNjk0XHVjOTk4IFx1YjljZVx1Yzc0MCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM1ZDBcdWMxMWNcdWIyOTQgR1BTIFx1YjEyNFx1YmU0NFx1YWM4Y1x1Yzc3NFx1YzE1OCBcdWM3YTVcdWJlNDRcdWFjMDAgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViMTI0XHViZTQ0XHVhYzhjXHVjNzc0XHVjMTU4XHVjNzQwIFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVjZDljXHViYzFjXHVjODEwXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFjODBcdWMwYzlcdWQ1NzQgXHVjOTAwXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWQ1MFx1ZDFiNSBcdWMwYzFcdWQ2NjlcdWM3NDQgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY5XHVjMmVjXHVkNTVjIFx1YWQ1MFx1ZDFiNSBcdWM4MTVcdWNjYjRcdWI5N2MgXHVhY2JkXHVkNWQ4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2MjRcdWM5YzEgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YjljYyBcdWMwYWNcdWM2YTkgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjEyNFx1YmU0NFx1YWM4Y1x1Yzc3NFx1YzE1OFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMTI0XHViZTQ0XHVhYzhjXHVjNzc0XHVjMTU4XHVjNzQwIFx1YzgwOFx1YjMwMFx1Yjg1YyBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzhmY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWFjNzBcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM3MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViNzgwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWIzYzRcdWI4NWNcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIzYzRcdWI4NWMgXHVjOWMwXHViM2M0XHVhYzAwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDQgXHViNTRjXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNmQwXHVjNzQwIFx1YzdhNVx1YzE4Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFx1YzEyMFx1Yzc0MCBcdWIyZThcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjMmRjXHVjNzkxXHVjODEwXHVjNzQwIFMsIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc0MCBEXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWQ3NVx1Yzc0MCBcdWMxMjBcdWM3NDAgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIChcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWIyOTQgXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQpXHVhYzcwXHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWFjYmRcdWI4NWNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhY2JkXHViODVjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVhYzcwXHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YWM3MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHViNDFjXHViMmU0LiBcdWI2MTAsIFx1YWM3MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FsbW9zdC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzRweDsgd2lkdGg6MjY1cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3YTVcdWMxOGNcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgNTAwKVx1YWNmYyBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMjE4IE0gKDEgJmxlOyBNICZsZTsgMTA8c3VwPjQ8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzdhNVx1YzE4Y1x1YjI5NCAwXHViZDgwXHVkMTMwIE4tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWM3OTFcdWM4MTAgU1x1YzY0MCBcdWIzYzRcdWNjMjlcdWM4MTAgRFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChTICZuZTsgRDsgMCAmbGU7IFMsIEQgJmx0OyBOKSBcdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNCBVLCBWLCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFUgJm5lOyBWIDsgMCAmbGU7IFUsIFYgJmx0OyBOOyAxICZsZTsgUCAmbGU7IDEwPHN1cD4zPFwvc3VwPikgXHVjNzc0IFx1YjczYlx1Yzc0MCBVXHVjNWQwXHVjMTFjIFZcdWI4NWMgXHVhYzAwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgUFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFVcdWM1ZDBcdWMxMWMgVlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzc0XHViMmU0LiBcdWI2MTAsIFVcdWM1ZDBcdWMxMWMgVlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHVjNjQwIFZcdWM1ZDBcdWMxMWMgVVx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWIzYzRcdWI4NWNcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjNzBcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWM3MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU3MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbG1vc3QgU2hvcnRlc3QgUGF0aCIsImRlc2NyaXB0aW9uIjoiPHA+RmluZGluZyB0aGUgc2hvcnRlc3QgcGF0aCB0aGF0IGdvZXMgZnJvbSBhIHN0YXJ0aW5nIHBvaW50IHRvIGEgZGVzdGluYXRpb24gcG9pbnQgZ2l2ZW4gYSBzZXQgb2YgcG9pbnRzIGFuZCByb3V0ZSBsZW5ndGhzIGNvbm5lY3RpbmcgdGhlbSBpcyBhbiBhbHJlYWR5IHdlbGwga25vd24gcHJvYmxlbSwgYW5kIGl0JnJzcXVvO3MgZXZlbiBwYXJ0IG9mIG91ciBkYWlseSBsaXZlcywgYXMgc2hvcnRlc3QgcGF0aCBwcm9ncmFtcyBhcmUgd2lkZWx5IGF2YWlsYWJsZSBub3dhZGF5cy48XC9wPlxyXG5cclxuPHA+TW9zdCBwZW9wbGUgdXN1YWxseSBsaWtlIHZlcnkgbXVjaCB0aGVzZSBhcHBsaWNhdGlvbnMgYXMgdGhleSBtYWtlIHRoZWlyIGxpdmVzIGVhc2llci4gV2VsbCwgbWF5YmUgbm90IHRoYXQgbXVjaCBlYXNpZXIuPFwvcD5cclxuXHJcbjxwPk5vdyB0aGF0IGFsbW9zdCBldmVyeW9uZSBjYW4gaGF2ZSBhY2Nlc3MgdG8gR1BTIG5hdmlnYXRpb24gZGV2aWNlcyBhYmxlIHRvIGNhbGN1bGF0ZSBzaG9ydGVzdCBwYXRocywgbW9zdCByb3V0ZXMgdGhhdCBmb3JtIHRoZSBzaG9ydGVzdCBwYXRoIGFyZSBnZXR0aW5nIHNsb3dlciBiZWNhdXNlIG9mIGhlYXZ5IHRyYVx1ZmIwM2MuIEFzIG1vc3QgcGVvcGxlIHRyeSB0byBmb2xsb3cgdGhlIHNhbWUgcGF0aCwgaXQmcnNxdW87cyBub3Qgd29ydGggaXQgYW55bW9yZSB0byBmb2xsb3cgdGhlc2UgZGlyZWN0aW9ucy48XC9wPlxyXG5cclxuPHA+V2l0aCB0aGlzIGluIGhpcyBtaW5kLCB5b3VyIGJvc3MgYXNrcyB5b3UgdG8gZGV2ZWxvcCBhIG5ldyBhcHBsaWNhdGlvbiB0aGF0IG9ubHkgaGUgd2lsbCBoYXZlIGFjY2VzcyB0bywgdGh1cyBzYXZpbmcgaGltIHRpbWUgd2hlbmV2ZXIgaGUgaGFzIGEgbWVldGluZyBvciBhbnkgdXJnZW50IGV2ZW50LiBIZSBhc2tzIHlvdSB0aGF0IHRoZSBwcm9ncmFtIG11c3QgYW5zd2VyIG5vdCB0aGUgc2hvcnRlc3QgcGF0aCwgYnV0IHRoZSBhbG1vc3Qgc2hvcnRlc3QgcGF0aC4gSGUgZGVcdWZiMDFuZXMgdGhlIGFsbW9zdCBzaG9ydGVzdCBwYXRoIGFzIHRoZSBzaG9ydGVzdCBwYXRoIHRoYXQgZ29lcyBmcm9tIGEgc3RhcnRpbmcgcG9pbnQgdG8gYSBkZXN0aW5hdGlvbiBwb2ludCBzdWNoIHRoYXQgbm8gcm91dGUgYmV0d2VlbiB0d28gY29uc2VjdXRpdmUgcG9pbnRzIGJlbG9uZ3MgdG8gYW55IHNob3J0ZXN0IHBhdGggZnJvbSB0aGUgc3RhcnRpbmcgcG9pbnQgdG8gdGhlIGRlc3RpbmF0aW9uLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgc3VwcG9zZSB0aGUgXHVmYjAxZ3VyZSBiZWxvdyByZXByZXNlbnRzIHRoZSBtYXAgZ2l2ZW4sIHdpdGggY2lyY2xlcyByZXByZXNlbnRpbmcgbG9jYXRpb24gcG9pbnRzLCBhbmQgbGluZXMgcmVwcmVzZW50aW5nIGRpcmVjdCwgb25lLXdheSByb3V0ZXMgd2l0aCBsZW5ndGhzIGluZGljYXRlZC4gVGhlIHN0YXJ0aW5nIHBvaW50IGlzIG1hcmtlZCBhcyBTIGFuZCB0aGUgZGVzdGluYXRpb24gcG9pbnQgaXMgbWFya2VkIGFzIEQuIFRoZSBib2xkIGxpbmVzIGJlbG9uZyB0byBhIHNob3J0ZXN0IHBhdGggKGluIHRoaXMgY2FzZSB0aGVyZSBhcmUgdHdvIHNob3J0ZXN0IHBhdGhzLCBlYWNoIHdpdGggdG90YWwgbGVuZ3RoIDQpLiBUaHVzLCB0aGUgYWxtb3N0IHNob3J0ZXN0IHBhdGggd291bGQgYmUgdGhlIG9uZSBpbmRpY2F0ZWQgYnkgZGFzaGVkIGxpbmVzICh0b3RhbCBsZW5ndGggNSksIGFzIG5vIHJvdXRlIGJldHdlZW4gdHdvIGNvbnNlY3V0aXZlIHBvaW50cyBiZWxvbmdzIHRvIGFueSBzaG9ydGVzdCBwYXRoLiBOb3RpY2UgdGhhdCB0aGVyZSBjb3VsZCBleGlzdCBtb3JlIHRoYW4gb25lIHBvc3NpYmxlIGFuc3dlciwgZm9yIGluc3RhbmNlIGlmIHRoZSByb3V0ZSB3aXRoIGxlbmd0aCAzIGhhZCBsZW5ndGggMS4gVGhlcmUgY291bGQgZXhpc3Qgbm8gcG9zc2libGUgYW5zd2VyIGFzIHdlbGwuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYWxtb3N0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NHB4OyB3aWR0aDoyNjVweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgyICZsZTsgTiAmbGU7IDUwMCkgYW5kIE0gKDEgJmxlOyBNICZsZTsgMTA8c3VwPjQ8XC9zdXA+KSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCBpbmRpY2F0aW5nIHJlc3BlY3RpdmVseSB0aGUgbnVtYmVyIG9mIHBvaW50cyBpbiB0aGUgbWFwIGFuZCB0aGUgbnVtYmVyIG9mIGV4aXN0aW5nIG9uZS13YXkgcm91dGVzIGNvbm5lY3RpbmcgdHdvIHBvaW50cyBkaXJlY3RseS4gRWFjaCBwb2ludCBpcyBpZGVudGlcdWZiMDFlZCBieSBhbiBpbnRlZ2VyIGJldHdlZW4gMCBhbmQgTiAmbWludXM7IDEuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUyBhbmQgRCwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCBpbmRpY2F0aW5nIHJlc3BlY3RpdmVseSB0aGUgc3RhcnRpbmcgYW5kIHRoZSBkZXN0aW5hdGlvbiBwb2ludHMgKFMgJm5lOyBEOyAwICZsZTsgUywgRCAmbHQ7IE4pLiBFYWNoIG9uZSBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgVSwgViBhbmQgUCAoVSAmbmU7IFYgOyAwICZsZTsgVSwgViAmbHQ7IE47IDEgJmxlOyBQICZsZTsgMTA8c3VwPjM8XC9zdXA+KSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIGluZGljYXRpbmcgdGhlIGV4aXN0ZW5jZSBvZiBhIG9uZS13YXkgcm91dGUgZnJvbSBVIHRvIFYgd2l0aCBkaXN0YW5jZSBQLiBUaGVyZSBpcyBhdCBtb3N0IG9uZSByb3V0ZSBmcm9tIGEgZ2l2ZW4gcG9pbnQgVSB0byBhIGdpdmVuIHBvaW50IFYgLCBidXQgbm90aWNlIHRoYXQgdGhlIGV4aXN0ZW5jZSBvZiBhIHJvdXRlIGZyb20gVSB0byBWIGRvZXMgbm90IGltcGx5IHRoZXJlIGlzIGEgcm91dGUgZnJvbSBWIHRvIFUsIGFuZCwgaWYgc3VjaCByb2FkIGV4aXN0cywgaXQgY2FuIGhhdmUgYSBkaVx1ZmIwMGVyZW50IGxlbmd0aC4gVGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25seSB0d28gemVyb3Mgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHlvdXIgcHJvZ3JhbSBtdXN0IHByaW50IGEgc2luZ2xlIGxpbmUsIGNvbnRhaW5pbmcgLTEgaWYgaXQgaXMgbm90IHBvc3NpYmxlIHRvIG1hdGNoIHRoZSByZXF1aXJlbWVudHMsIG9yIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBsZW5ndGggb2YgdGhlIGFsbW9zdCBzaG9ydGVzdCBwYXRoIGZvdW5kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Latin America > South America Regional Contests 2008 A번