시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 662 242 172 38.137%

문제

미힐 더 라위터르는 네델란드의 역사에서 가장 유명한 제독이다. 그는 17세기에 벌어진 영국-네델란드 전쟁에서 전공을 세웠다.

라위터르가 살던 시절에 그래프 이론이 연구되기 시작했고, 제독은 이론을 해전 계획에 자주 이용했다. 바다 위의 중간 지점은 정점으로 나타낼 수 있고, 각 중간 지점에서 이동할 수 있는 뱃길은 방향성이 있는 간선으로 나타나 있다. 두 중간 지점 W1와 W2사이에 뱃길 W1 → W2는 최대 한 개 있을 수 있다. 각 간선의 가중치는 그 뱃길을 안전하게 이동하기 위해 발사해야 하는 포탄의 수이다. 

라위터르의 가장 유명한 전술은 "De Ruyter Manoeuvre"이다. 이 전술은 한 중간 지점에서 두 전함이 서로 다른 방향으로 출발을 한다. 그 다음 적함과 전투를 하면서 이동한 다음 목적지에서 다시 만나는 전술이다. 이 전술에서 두 전함은 항상 겹치지 않는 뱃길을 택해야 하며, 출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안된다.

라위터르는 돈을 낭비하는 것을 좋아하지 않는다. 따라서, 포탄을 가장 적게 발사하는 뱃길을 택하려고 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 입력의 끝은 EOF로 확인할 수 있다.

테스트 케이스의 첫째 줄에는 중간 지점의 수 v와 뱃길의 수 e가 주어진다. (3 ≤ v ≤ 1000, 3 ≤ e ≤ 10000) 다음 e개 줄에는 뱃길의 정보 ai, bi, ci가 주어진다. (1 ≤ ai, bi ≤ v, ai ≠ bi, 1 ≤ ci ≤ 100) ai는 뱃길의 시작 지점, bi는 도착 지점, ci는 그 뱃길로 이동할 때 발사해야 하는 포탄의 수이다.

전술의 시작 지점은 1이고, 목적지는 v이다. 항상 1과 v사이에 겹치지 않는 경로가 적어도 두 개 있다.

출력

각 테스트 케이스에 대해서, 두 전함이 전술을 따르면서 발사해야 하는 포탄의 최소 개수를 출력한다.

예제 입력 1

6 11
1 2 23
1 3 12
1 4 99
2 5 17
2 6 73
3 5 3
3 6 21
4 6 8
5 2 33
5 4 5
6 5 20
3 3
1 3 1
1 2 5
2 3 5

예제 출력 1

86
11

힌트

두 함선(빨강, 파랑)은 1에서 시작해서 6에서 만난다. 빨간 함선은 1 → 3 → 6 (총 33개 포탄)으로 이동하고, 파란 함선은 1 → 2 → 5 → 4 → 6 (총 53개 포탄)으로 이동한다. 두 경로에서 출발과 도착을 제외하면 중복되는 정점과 간선이 없다.

W3sicHJvYmxlbV9pZCI6IjM2NDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MWNcdWIzYzUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmOFx1ZDc5MCBcdWIzNTQgXHViNzdjXHVjNzA0XHVkMTMwXHViOTc0XHViMjk0IFx1YjEyNFx1YjM3OFx1Yjc4MFx1YjRkY1x1Yzc1OCBcdWM1ZWRcdWMwYWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM4MWNcdWIzYzVcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjI5NCAxN1x1YzEzOFx1YWUzMFx1YzVkMCBcdWJjOGNcdWM1YjRcdWM5YzQgXHVjNjAxXHVhZDZkLVx1YjEyNFx1YjM3OFx1Yjc4MFx1YjRkYyBcdWM4MDRcdWM3YzFcdWM1ZDBcdWMxMWMgXHVjODA0XHVhY2Y1XHVjNzQ0IFx1YzEzOFx1YzZlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzdjXHVjNzA0XHVkMTMwXHViOTc0XHVhYzAwIFx1YzBiNFx1YjM1OCBcdWMyZGNcdWM4MDhcdWM1ZDAgXHVhZGY4XHViNzk4XHVkNTA0IFx1Yzc3NFx1Yjg2MFx1Yzc3NCBcdWM1ZjBcdWFkNmNcdWI0MThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHVhY2UwLCBcdWM4MWNcdWIzYzVcdWM3NDAgXHVjNzc0XHViODYwXHVjNzQ0Jm5ic3A7XHVkNTc0XHVjODA0IFx1YWNjNFx1ZDY4ZFx1YzVkMCBcdWM3OTBcdWM4ZmMgXHVjNzc0XHVjNmE5XHVkNTg4XHViMmU0LiBcdWJjMTRcdWIyZTQgXHVjNzA0XHVjNzU4IFx1YzkxMVx1YWMwNCBcdWM5YzBcdWM4MTBcdWM3NDAgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjNDNcdWFlMzhcdWM3NDAmbmJzcDtcdWJjMjlcdWQ1YTVcdWMxMzFcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOTggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMCBXMVx1YzY0MCBXMlx1YzBhY1x1Yzc3NFx1YzVkMCBcdWJjNDNcdWFlMzgmbmJzcDtXMSAmcmFycjsgVzJcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7XHVhYzAxIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgXHVhZGY4IFx1YmM0M1x1YWUzOFx1Yzc0NCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjMWNcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDNlY1x1ZDBjNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yjc3Y1x1YzcwNFx1ZDEzMFx1Yjk3NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzgwNFx1YzIyMFx1Yzc0MCAmcXVvdDtEZSBSdXl0ZXIgTWFub2V1dnJlJnF1b3Q7XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjODA0XHVjMjIwXHVjNzQwIFx1ZDU1YyBcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWM4MDRcdWQ1NjhcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjZDljXHViYzFjXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM4MDFcdWQ1NjhcdWFjZmMgXHVjODA0XHVkMjJjXHViOTdjIFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NWMgXHViMmU0XHVjNzRjIFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMFx1YzExYyBcdWIyZTRcdWMyZGMgXHViOWNjXHViMDk4XHViMjk0IFx1YzgwNFx1YzIyMFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzgwNFx1YzIyMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODA0XHVkNTY4XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmM0M1x1YWUzOFx1Yzc0NCZuYnNwO1x1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Y2Q5Y1x1YmMxY1x1YWNmYyBcdWJhYTlcdWM4MDFcdWM5YzBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNzc0XHViMDk4IFx1YWMxOVx1Yzc0MCBcdWJjNDNcdWFlMzhcdWM3NDQmbmJzcDtcdWM5YzBcdWIwOThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI3N2NcdWM3MDRcdWQxMzBcdWI5NzRcdWIyOTQgXHViM2M4XHVjNzQ0IFx1YjBhZFx1YmU0NFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWQzZWNcdWQwYzRcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWJjMWNcdWMwYWNcdWQ1NThcdWIyOTQgXHViYzQzXHVhZTM4XHVjNzQ0Jm5ic3A7XHVkMGRkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0MCBFT0ZcdWI4NWMgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNzU4IFx1YzIxOCB2XHVjNjQwIFx1YmM0M1x1YWUzOFx1Yzc1OCBcdWMyMTggZVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgdiAmbGU7IDEwMDAsIDMgJmxlOyBlICZsZTsgMTAwMDApJm5ic3A7XHViMmU0XHVjNzRjIGVcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmM0M1x1YWUzOFx1Yzc1OCBcdWM4MTVcdWJjZjQgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+LCBjPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+ICZsZTsgdiwgYTxzdWI+aTxcL3N1Yj4gJm5lOyBiPHN1Yj5pPFwvc3ViPiwgMSAmbGU7IGM8c3ViPmk8XC9zdWI+ICZsZTsgMTAwKSBhPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWJjNDNcdWFlMzhcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMCwgYjxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViM2M0XHVjYzI5IFx1YzljMFx1YzgxMCwgYzxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVhZGY4IFx1YmM0M1x1YWUzOFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjIFx1YmMxY1x1YzBhY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkM2VjXHVkMGM0XHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODA0XHVjMjIwXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM5YzBcdWM4MTBcdWM3NDAgMVx1Yzc3NFx1YWNlMCwgXHViYWE5XHVjODAxXHVjOWMwXHViMjk0IHZcdWM3NzRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSAxXHVhY2ZjIHZcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWFjMWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViNDUwIFx1YzgwNFx1ZDU2OFx1Yzc3NCBcdWM4MDRcdWMyMjBcdWM3NDQgXHViNTMwXHViOTc0XHViYTc0XHVjMTFjIFx1YmMxY1x1YzBhY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkM2VjXHVkMGM0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FkbWlyYWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mjg0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo0MTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVkNTY4XHVjMTIwKFx1YmU2OFx1YWMxNSwgXHVkMzBjXHViNzkxKVx1Yzc0MCAxXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyA2XHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5Y1x1YjJlNC4gXHViZTY4XHVhYzA0IFx1ZDU2OFx1YzEyMFx1Yzc0MCAxICZyYXJyOyZuYnNwOzMmbmJzcDsmcmFycjsmbmJzcDs2IChcdWNkMWQgMzNcdWFjMWMgXHVkM2VjXHVkMGM0KVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjZTAsIFx1ZDMwY1x1Yjc4MCBcdWQ1NjhcdWMxMjBcdWM3NDAgMSZuYnNwOyZyYXJyOyZuYnNwOzImbmJzcDsmcmFycjsmbmJzcDs1Jm5ic3A7JnJhcnI7Jm5ic3A7NCZuYnNwOyZyYXJyOyZuYnNwOzYgKFx1Y2QxZCA1M1x1YWMxYyBcdWQzZWNcdWQwYzQpXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YWNiZFx1Yjg1Y1x1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWFjZmMgXHViM2M0XHVjYzI5XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YmE3NCBcdWM5MTFcdWJjZjVcdWI0MThcdWIyOTQgXHVjODE1XHVjODEwXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWRtaXJhbCIsImRlc2NyaXB0aW9uIjoiPHA+TWljaGllbCBBZHJpYWVuc3pvb24gZGUgUnV5dGVyIGlzIHRoZSBtb3N0IGZhbW91cyBhZG1pcmFsIGluIER1dGNoIGhpc3RvcnkgYW5kIGlzIHdlbGwga25vd24gZm9yIGhpcyByb2xlIGluIHRoZSBBbmdsby1EdXRjaCBXYXJzIG9mIHRoZSAxN3RoIGNlbnR1cnkuIERlIFJ1eXRlciBwZXJzb25hbGx5IGNvbW1hbmRlZCBhIFx1ZmIwMmFnc2hpcCBhbmQgaXNzdWVkIGNvbW1hbmRzIHRvIGFsbGllZCB3YXJzaGlwcyBkdXJpbmcgbmF2YWwgYmF0dGxlcy48XC9wPlxyXG5cclxuPHA+SW4gRGUgUnV5dGVyJnJzcXVvO3MgdGltZSwgZ3JhcGggdGhlb3J5IGhhZCBqdXN0IGJlZW4gaW52ZW50ZWQgYW5kIHRoZSBhZG1pcmFsIHVzZWQgaXQgdG8gaGlzIGdyZWF0IGFkdmFudGFnZSBpbiBwbGFubmluZyBoaXMgbmF2YWwgYmF0dGxlcy4gV2F5cG9pbnRzIGF0IHNlYSBhcmUgcmVwcmVzZW50ZWQgYnkgdmVydGljZXMsIGFuZCBwb3NzaWJsZSBwYXNzYWdlcyBmcm9tIG9uZSB3YXlwb2ludCB0byBhbm90aGVyIGFyZSByZXByZXNlbnRlZCBhcyBkaXJlY3RlZCBlZGdlcy4gR2l2ZW4gYW55IHR3byB3YXlwb2ludHMgVzEgYW5kIFcyLCB0aGVyZSBpcyBhdCBtb3N0IG9uZSBwYXNzYWdlIFcxICZyYXJyOyBXMi4gRWFjaCBkaXJlY3RlZCBlZGdlIGlzIG1hcmtlZCB3aXRoIHRoZSBudW1iZXIgb2YgY2Fubm9uYmFsbHMgdGhhdCBuZWVkIHRvIGJlIFx1ZmIwMXJlZCBpbiBvcmRlciB0byBzYWZlbHkgbW92ZSBhIHNoaXAgYWxvbmcgdGhhdCBlZGdlLCBzaW5raW5nIHRoZSBlbmVteSBzaGlwcyBlbmNvdW50ZXJlZCBhbG9uZyB0aGUgd2F5LjxcL3A+XHJcblxyXG48cD5PbmUgb2YgRGUgUnV5dGVyJnJzcXVvO3MgbW9zdCBzdWNjZXNzZnVsIHRhY3RpY3Mgd2FzIHRoZSBEZSBSdXl0ZXIgTWFub2V1dnJlLiBIZXJlLCB0d28gd2Fyc2hpcHMgc3RhcnQgYXQgdGhlIHNhbWUgd2F5cG9pbnQsIGFuZCBzcGxpdCB1cCBhbmQgXHVmYjAxZ2h0IHRoZWlyIHdheSB0aHJvdWdoIHRoZSBlbmVteSBcdWZiMDJlZXQsIGpvaW5pbmcgdXAgYWdhaW4gYXQgYSBkZXN0aW5hdGlvbiB3YXlwb2ludC4gVGhlIG1hbm9ldXZyZSBwcmVzY3JpYmVzIHRoYXQgdGhlIHR3byB3YXJzaGlwcyB0YWtlIGRpc2p1bmN0IHJvdXRlcywgbWVhbmluZyB0aGF0IHRoZXkgbXVzdCBub3QgdmlzaXQgdGhlIHNhbWUgd2F5cG9pbnQgKG90aGVyIHRoYW4gdGhlIHN0YXJ0IGFuZCBlbmQtcG9pbnRzKSwgb3IgdXNlIHRoZSBzYW1lIHBhc3NhZ2UgZHVyaW5nIHRoZSBiYXR0bGUuPFwvcD5cclxuXHJcbjxwPkJlaW5nIER1dGNoLCBBZG1pcmFsIERlIFJ1eXRlciBkaWQgbm90IGxpa2UgdG8gd2FzdGUgbW9uZXk7IGluIDE3dGggY2VudHVyeSBuYXZhbCB3YXJmYXJlLCB0aGlzIG1lYW50IFx1ZmIwMXJpbmcgYXMgZmV3IGV4cGVuc2l2ZSBjYW5ub25iYWxscyBhcyBwb3NzaWJsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGlucHV0IGNvbnNpc3RzIG9mOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyB2ICgzICZsZTsgdiAmbGU7IDEwMDApIGFuZCBlICgzICZsZTsgZSAmbGU7IDEwMDAwKSwgdGhlIG51bWJlciBvZiB3YXlwb2ludHMgYW5kIHBhc3NhZ2VzLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPlRoZW4sIGUgbGluZXMgZm9sbG93OiBmb3IgZWFjaCBwYXNzYWdlLCBhIGxpbmUgY29udGFpbmluZyB0aHJlZSBpbnRlZ2VyczpcclxuXHQ8b2w+XHJcblx0XHQ8bGk+YTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgdiksIHRoZSBzdGFydGluZy1wb2ludCBvZiBhIHBhc3NhZ2UsIHdoaWNoIGlzIHJlcHJlc2VudGVkIGJ5IGEgd2F5cG9pbnQ7PFwvbGk+XHJcblx0XHQ8bGk+YjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBiPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgdikgYW5kIChhPHN1Yj5pPFwvc3ViPiAmbmU7IGI8c3ViPmk8XC9zdWI+KSwgdGhlIGVuZC1wb2ludCBvZiBhIHBhc3NhZ2UsIHdoaWNoIGlzIHJlcHJlc2VudGVkIGJ5IGEgd2F5cG9pbnQuIEFsbCBwYXNzYWdlcyBhcmUgZGlyZWN0ZWQgcGFzc2FnZXM7PFwvbGk+XHJcblx0XHQ8bGk+YzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBjPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBjYW5ub25iYWxscyB0aGF0IGFyZSBcdWZiMDFyZWQgd2hlbiB0cmF2ZWxsaW5nIGFsb25nIHRoaXMgcGFzc2FnZS48XC9saT5cclxuXHQ8XC9vbD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgc3RhcnRpbmcgd2F5cG9pbnQgaXMgMSBhbmQgdGhlIGRlc3RpbmF0aW9uIHdheXBvaW50IGlzIHYuIFRoZXJlIGFyZSBhbHdheXMgYXQgbGVhc3QgdHdvIGRpc2p1bmN0IHJvdXRlcyBmcm9tIHdheXBvaW50IDEgdG8gd2F5cG9pbnQgdi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBvdXRwdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlcjogdGhlIHNtYWxsZXN0IHBvc3NpYmxlIHN1bSBvZiBjYW5ub25iYWxscyBcdWZiMDFyZWQgYnkgYm90aCBzaGlwcyB3aGVuIHJlYWNoaW5nIHRoZSBkZXN0aW5hdGlvbiB3YXlwb2ludC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9hZG1pcmFsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4NHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NDEzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IEEgcGFydGljdWxhciBpbnN0YW5jZSBvZiBEZSBSdXl0ZXImcnNxdW87cyB0YWN0aWMsIHZpc3VhbGlzZWQgYXMgYSBncmFwaC4gVHdvIHNoaXBzICgmbHNxdW87cmVkJnJzcXVvOyBhbmQgJmxzcXVvO2JsdWUmcnNxdW87KSBtb3ZlIGZyb20gYSBzaGFyZWQgc3RhcnRpbmcgcG9pbnQgKDEpIHRvIGEgc2hhcmVkIGVuZHBvaW50ICg2KS4gVGhlIHJlZCBzaGlwJnJzcXVvO3Mgcm91dGUgaXMgMSAmcmFycjsgMyAmcmFycjsgNiAoXHVmYjAxcmluZyAzMyBjYW5vbmJhbGxzIGFsb25nIHRoZSB3YXkpOyB0aGUgYmx1ZSBzaGlwJnJzcXVvO3Mgcm91dGUgaXMgMSAmcmFycjsgMiAmcmFycjsgNSAmcmFycjsgNCAmcmFycjsgNiAoXHVmYjAxcmluZyA1MyBjYW5vbmJhbGxzIGFsb25nIHRoZSB3YXkpLiBJbiB0b3RhbCwgODYgY2Fub25iYWxscyBhcmUgXHVmYjAxcmVkIGR1cmluZyB0aGUgbWFub2V1dnJlLiBFeGNlcHQgZm9yIHRoZSBzdGFydC0gYW5kIGVuZC1wb2ludCwgbm8gdmVydGljZXMgb3IgZWRnZXMgYXJlIHZpc2l0ZWQgYnkgYm90aCBzaGlwcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 A번