시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 777 296 208 38.590%

문제

미힐 더 라위터르는 네델란드의 역사에서 가장 유명한 제독이다. 그는 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+XHViNzdjXHVjNzA0XHVkMTMwXHViOTc0XHVhYzAwIFx1YzBiNFx1YjM1OCBcdWMyZGNcdWM4MDhcdWM1ZDAgXHVhZGY4XHViNzk4XHVkNTA0IFx1Yzc3NFx1Yjg2MFx1Yzc3NCBcdWM1ZjBcdWFkNmNcdWI0MThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHVhY2UwLCBcdWM4MWNcdWIzYzVcdWM3NDAgXHVjNzc0XHViODYwXHVjNzQ0Jm5ic3A7XHVkNTc0XHVjODA0IFx1YWNjNFx1ZDY4ZFx1YzVkMCBcdWM3OTBcdWM4ZmMgXHVjNzc0XHVjNmE5XHVkNTg4XHViMmU0LiBcdWJjMTRcdWIyZTQgXHVjNzA0XHVjNzU4IFx1YzkxMVx1YWMwNCBcdWM5YzBcdWM4MTBcdWM3NDAgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjNDNcdWFlMzhcdWM3NDAmbmJzcDtcdWJjMjlcdWQ1YTVcdWMxMzFcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOTggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMCBXMVx1YzY0MCBXMlx1YzBhY1x1Yzc3NFx1YzVkMCBcdWJjNDNcdWFlMzgmbmJzcDtXMSAmcmFycjsgVzJcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7XHVhYzAxIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgXHVhZGY4IFx1YmM0M1x1YWUzOFx1Yzc0NCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjMWNcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDNlY1x1ZDBjNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yjc3Y1x1YzcwNFx1ZDEzMFx1Yjk3NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzgwNFx1YzIyMFx1Yzc0MCAmcXVvdDtEZSBSdXl0ZXIgTWFub2V1dnJlJnF1b3Q7XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjODA0XHVjMjIwXHVjNzQwIFx1ZDU1YyBcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWM4MDRcdWQ1NjhcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjZDljXHViYzFjXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM4MDFcdWQ1NjhcdWFjZmMgXHVjODA0XHVkMjJjXHViOTdjIFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NWMgXHViMmU0XHVjNzRjIFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMFx1YzExYyBcdWIyZTRcdWMyZGMgXHViOWNjXHViMDk4XHViMjk0IFx1YzgwNFx1YzIyMFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzgwNFx1YzIyMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODA0XHVkNTY4XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmM0M1x1YWUzOFx1Yzc0NCZuYnNwO1x1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Y2Q5Y1x1YmMxY1x1YWNmYyBcdWJhYTlcdWM4MDFcdWM5YzBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNzc0XHViMDk4IFx1YWMxOVx1Yzc0MCBcdWJjNDNcdWFlMzhcdWM3NDQmbmJzcDtcdWM5YzBcdWIwOThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzdjXHVjNzA0XHVkMTMwXHViOTc0XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWIwYWRcdWJlNDRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVkM2VjXHVkMGM0XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHViYzFjXHVjMGFjXHVkNTU4XHViMjk0IFx1YmM0M1x1YWUzOFx1Yzc0NCZuYnNwO1x1ZDBkZFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM3NDAgRU9GXHViODVjIFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWMyMTggdlx1YzY0MCBcdWJjNDNcdWFlMzhcdWM3NTggXHVjMjE4IGVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IHYgJmxlOyAxMDAwLCAzICZsZTsgZSAmbGU7IDEwMDAwKSZuYnNwO1x1YjJlNFx1Yzc0YyBlXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjNDNcdWFlMzhcdWM3NTggXHVjODE1XHViY2Y0IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiwgYzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IHYsIGE8c3ViPmk8XC9zdWI+ICZuZTsgYjxzdWI+aTxcL3N1Yj4sIDEgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCkgYTxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViYzQzXHVhZTM4XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM5YzBcdWM4MTAsIGI8c3ViPmk8XC9zdWI+XHViMjk0IFx1YjNjNFx1Y2MyOSBcdWM5YzBcdWM4MTAsIGM8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWRmOCBcdWJjNDNcdWFlMzhcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YyBcdWJjMWNcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDNlY1x1ZDBjNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1YzIyMFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjOWMwXHVjODEwXHVjNzQwIDFcdWM3NzRcdWFjZTAsIFx1YmFhOVx1YzgwMVx1YzljMFx1YjI5NCB2XHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgMVx1YWNmYyB2XHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0NTAgXHVhYzFjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjQ1MCBcdWM4MDRcdWQ1NjhcdWM3NzQgXHVjODA0XHVjMjIwXHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YmE3NFx1YzExYyBcdWJjMWNcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDNlY1x1ZDBjNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9hZG1pcmFsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4NHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NDEzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1ZDU2OFx1YzEyMChcdWJlNjhcdWFjMTUsIFx1ZDMwY1x1Yjc5MSlcdWM3NDAgMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgNlx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOWNcdWIyZTQuIFx1YmU2OFx1YWMwNCBcdWQ1NjhcdWMxMjBcdWM3NDAgMSAmcmFycjsmbmJzcDszJm5ic3A7JnJhcnI7Jm5ic3A7NiAoXHVjZDFkIDMzXHVhYzFjIFx1ZDNlY1x1ZDBjNClcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhY2UwLCBcdWQzMGNcdWI3ODAgXHVkNTY4XHVjMTIwXHVjNzQwIDEmbmJzcDsmcmFycjsmbmJzcDsyJm5ic3A7JnJhcnI7Jm5ic3A7NSZuYnNwOyZyYXJyOyZuYnNwOzQmbmJzcDsmcmFycjsmbmJzcDs2IChcdWNkMWQgNTNcdWFjMWMgXHVkM2VjXHVkMGM0KVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NThcdWJhNzQgXHVjOTExXHViY2Y1XHViNDE4XHViMjk0IFx1YzgxNVx1YzgxMFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY0MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFkbWlyYWwiLCJkZXNjcmlwdGlvbiI6IjxwPk1pY2hpZWwgQWRyaWFlbnN6b29uIGRlIFJ1eXRlciBpcyB0aGUgbW9zdCBmYW1vdXMgYWRtaXJhbCBpbiBEdXRjaCBoaXN0b3J5IGFuZCBpcyB3ZWxsIGtub3duIGZvciBoaXMgcm9sZSBpbiB0aGUgQW5nbG8tRHV0Y2ggV2FycyBvZiB0aGUgMTd0aCBjZW50dXJ5LiBEZSBSdXl0ZXIgcGVyc29uYWxseSBjb21tYW5kZWQgYSBcdWZiMDJhZ3NoaXAgYW5kIGlzc3VlZCBjb21tYW5kcyB0byBhbGxpZWQgd2Fyc2hpcHMgZHVyaW5nIG5hdmFsIGJhdHRsZXMuPFwvcD5cclxuXHJcbjxwPkluIERlIFJ1eXRlciZyc3F1bztzIHRpbWUsIGdyYXBoIHRoZW9yeSBoYWQganVzdCBiZWVuIGludmVudGVkIGFuZCB0aGUgYWRtaXJhbCB1c2VkIGl0IHRvIGhpcyBncmVhdCBhZHZhbnRhZ2UgaW4gcGxhbm5pbmcgaGlzIG5hdmFsIGJhdHRsZXMuIFdheXBvaW50cyBhdCBzZWEgYXJlIHJlcHJlc2VudGVkIGJ5IHZlcnRpY2VzLCBhbmQgcG9zc2libGUgcGFzc2FnZXMgZnJvbSBvbmUgd2F5cG9pbnQgdG8gYW5vdGhlciBhcmUgcmVwcmVzZW50ZWQgYXMgZGlyZWN0ZWQgZWRnZXMuIEdpdmVuIGFueSB0d28gd2F5cG9pbnRzIFcxIGFuZCBXMiwgdGhlcmUgaXMgYXQgbW9zdCBvbmUgcGFzc2FnZSBXMSAmcmFycjsgVzIuIEVhY2ggZGlyZWN0ZWQgZWRnZSBpcyBtYXJrZWQgd2l0aCB0aGUgbnVtYmVyIG9mIGNhbm5vbmJhbGxzIHRoYXQgbmVlZCB0byBiZSBcdWZiMDFyZWQgaW4gb3JkZXIgdG8gc2FmZWx5IG1vdmUgYSBzaGlwIGFsb25nIHRoYXQgZWRnZSwgc2lua2luZyB0aGUgZW5lbXkgc2hpcHMgZW5jb3VudGVyZWQgYWxvbmcgdGhlIHdheS48XC9wPlxyXG5cclxuPHA+T25lIG9mIERlIFJ1eXRlciZyc3F1bztzIG1vc3Qgc3VjY2Vzc2Z1bCB0YWN0aWNzIHdhcyB0aGUgRGUgUnV5dGVyIE1hbm9ldXZyZS4gSGVyZSwgdHdvIHdhcnNoaXBzIHN0YXJ0IGF0IHRoZSBzYW1lIHdheXBvaW50LCBhbmQgc3BsaXQgdXAgYW5kIFx1ZmIwMWdodCB0aGVpciB3YXkgdGhyb3VnaCB0aGUgZW5lbXkgXHVmYjAyZWV0LCBqb2luaW5nIHVwIGFnYWluIGF0IGEgZGVzdGluYXRpb24gd2F5cG9pbnQuIFRoZSBtYW5vZXV2cmUgcHJlc2NyaWJlcyB0aGF0IHRoZSB0d28gd2Fyc2hpcHMgdGFrZSBkaXNqdW5jdCByb3V0ZXMsIG1lYW5pbmcgdGhhdCB0aGV5IG11c3Qgbm90IHZpc2l0IHRoZSBzYW1lIHdheXBvaW50IChvdGhlciB0aGFuIHRoZSBzdGFydCBhbmQgZW5kLXBvaW50cyksIG9yIHVzZSB0aGUgc2FtZSBwYXNzYWdlIGR1cmluZyB0aGUgYmF0dGxlLjxcL3A+XHJcblxyXG48cD5CZWluZyBEdXRjaCwgQWRtaXJhbCBEZSBSdXl0ZXIgZGlkIG5vdCBsaWtlIHRvIHdhc3RlIG1vbmV5OyBpbiAxN3RoIGNlbnR1cnkgbmF2YWwgd2FyZmFyZSwgdGhpcyBtZWFudCBcdWZiMDFyaW5nIGFzIGZldyBleHBlbnNpdmUgY2Fubm9uYmFsbHMgYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBpbnB1dCBjb25zaXN0cyBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgdiAoMyAmbGU7IHYgJmxlOyAxMDAwKSBhbmQgZSAoMyAmbGU7IGUgJmxlOyAxMDAwMCksIHRoZSBudW1iZXIgb2Ygd2F5cG9pbnRzIGFuZCBwYXNzYWdlcywgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG5cdDxsaT5UaGVuLCBlIGxpbmVzIGZvbGxvdzogZm9yIGVhY2ggcGFzc2FnZSwgYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgaW50ZWdlcnM6XHJcblx0PG9sPlxyXG5cdFx0PGxpPmE8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IHYpLCB0aGUgc3RhcnRpbmctcG9pbnQgb2YgYSBwYXNzYWdlLCB3aGljaCBpcyByZXByZXNlbnRlZCBieSBhIHdheXBvaW50OzxcL2xpPlxyXG5cdFx0PGxpPmI8c3ViPmk8XC9zdWI+ICgxICZsZTsgYjxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IHYpIGFuZCAoYTxzdWI+aTxcL3N1Yj4gJm5lOyBiPHN1Yj5pPFwvc3ViPiksIHRoZSBlbmQtcG9pbnQgb2YgYSBwYXNzYWdlLCB3aGljaCBpcyByZXByZXNlbnRlZCBieSBhIHdheXBvaW50LiBBbGwgcGFzc2FnZXMgYXJlIGRpcmVjdGVkIHBhc3NhZ2VzOzxcL2xpPlxyXG5cdFx0PGxpPmM8c3ViPmk8XC9zdWI+ICgxICZsZTsgYzxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgY2Fubm9uYmFsbHMgdGhhdCBhcmUgXHVmYjAxcmVkIHdoZW4gdHJhdmVsbGluZyBhbG9uZyB0aGlzIHBhc3NhZ2UuPFwvbGk+XHJcblx0PFwvb2w+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHN0YXJ0aW5nIHdheXBvaW50IGlzIDEgYW5kIHRoZSBkZXN0aW5hdGlvbiB3YXlwb2ludCBpcyB2LiBUaGVyZSBhcmUgYWx3YXlzIGF0IGxlYXN0IHR3byBkaXNqdW5jdCByb3V0ZXMgZnJvbSB3YXlwb2ludCAxIHRvIHdheXBvaW50IHYuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgb3V0cHV0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXI6IHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBzdW0gb2YgY2Fubm9uYmFsbHMgXHVmYjAxcmVkIGJ5IGJvdGggc2hpcHMgd2hlbiByZWFjaGluZyB0aGUgZGVzdGluYXRpb24gd2F5cG9pbnQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYWRtaXJhbC5wbmdcIiBzdHlsZT1cImhlaWdodDoyODRweDsgb3BhY2l0eTowLjk7IHdpZHRoOjQxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBBIHBhcnRpY3VsYXIgaW5zdGFuY2Ugb2YgRGUgUnV5dGVyJnJzcXVvO3MgdGFjdGljLCB2aXN1YWxpc2VkIGFzIGEgZ3JhcGguIFR3byBzaGlwcyAoJmxzcXVvO3JlZCZyc3F1bzsgYW5kICZsc3F1bztibHVlJnJzcXVvOykgbW92ZSBmcm9tIGEgc2hhcmVkIHN0YXJ0aW5nIHBvaW50ICgxKSB0byBhIHNoYXJlZCBlbmRwb2ludCAoNikuIFRoZSByZWQgc2hpcCZyc3F1bztzIHJvdXRlIGlzIDEgJnJhcnI7IDMgJnJhcnI7IDYgKFx1ZmIwMXJpbmcgMzMgY2Fub25iYWxscyBhbG9uZyB0aGUgd2F5KTsgdGhlIGJsdWUgc2hpcCZyc3F1bztzIHJvdXRlIGlzIDEgJnJhcnI7IDIgJnJhcnI7IDUgJnJhcnI7IDQgJnJhcnI7IDYgKFx1ZmIwMXJpbmcgNTMgY2Fub25iYWxscyBhbG9uZyB0aGUgd2F5KS4gSW4gdG90YWwsIDg2IGNhbm9uYmFsbHMgYXJlIFx1ZmIwMXJlZCBkdXJpbmcgdGhlIG1hbm9ldXZyZS4gRXhjZXB0IGZvciB0aGUgc3RhcnQtIGFuZCBlbmQtcG9pbnQsIG5vIHZlcnRpY2VzIG9yIGVkZ2VzIGFyZSB2aXNpdGVkIGJ5IGJvdGggc2hpcHMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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