시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 161 68 50 39.062%

문제

코리아 통신회사에서는 3인통화 서비스를 제공한다. 이 서비스에서는 두 사람이 아니라 세 사람이 통화할 수 있도록 해준다. 전화망은 스위치들을 연결하여 구성되어 있으며, 각 통화자들은 스위치에 연결하여 전화망에 접속한다. 두 스위치들은 양방향으로 신호를 보낼 수 있는 링크에 의하여 연결되어 있다. 모든 스위치들은 전화망에 의하여 연결되어 있어서 스위치에 접속한 사람들은 다른 스위치에 연결한 사람과 항상 통화할 수 있다. 전화망에서 두 개의 스위치를 연결하는 링크를 사용하는 비용은 주어져 있다.

통신회사에서는 이들 세 사람을 전화망을 통하여 연결해주는데, 가장 비용이 적게 되도록 연결하고자한다. 세 사람이 연결한 스위치가 주어졌을 때, 이 스위치들을 비용이 가장 적게 되도록 연결하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 두 개의 정수가 있다. 첫 번째 정수 n(1<=n<=1000) 는 전화망에 있는 스위치의 개수를 나타내며, 두 번째 정수 m은 스위치와 스위치를 연결하는 링크의 개수를 나타낸다. 단, 같은 스위치들을 연결하는 링크는 1 개 이상 존재하지 않는다. 각 스위치들은 1번부터 차례로 n 번 까지 번호가 부여된다. 다음 m개의 줄에는, 각 줄에 세 개의 정수가 주어진다. 처음의 두 개의 정수는 하나의 링크에 의하여 연결되는 두 스위치의 번호를 나타내며, 세 번째 정수는 그 링크를 사용하는 비용을 나타내는 양의 정수이다. 이 정수는 100 보다 작다. 입력의 마지막 줄에는 세 개의 정수가 주어 진다. 이 정수는 세 명의 통화자가 연결되어 있는 스위치 번호이며, 세 정수는 모두 다르다.

출력

첫 줄에는 3자 통화를 하는데 있어서 가장 적은 비용으로 통화할 때 드는 비용을 나타내는 정수와 세명의 통화자를 연결하는 네트워크 상에서의 링크의 수를 출력한다. 그 다음 줄부터 각 줄에는 하나의 링크에 연결되는 두 개의 스위치 번호를 출력한다. 비용이 최소가 되도록 연결하는 방법이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

8 12
1 2 20
2 3 8
2 4 3
2 5 3
2 6 6
3 5 2
3 6 9
4 7 5
5 6 1
5 7 7
6 8 4
7 8 6
1 4 6

예제 출력 1

27 4
1 2
2 4
2 5
5 6
W3sicHJvYmxlbV9pZCI6IjIzOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIzXHVjNzc4XHVkMWI1XHVkNjU0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNmNTRcdWI5YWNcdWM1NDQgXHVkMWI1XHVjMmUwXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjXHViMjk0IDNcdWM3NzhcdWQxYjVcdWQ2NTQgXHVjMTFjXHViZTQ0XHVjMmE0XHViOTdjIFx1YzgxY1x1YWNmNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzExY1x1YmU0NFx1YzJhNFx1YzVkMFx1YzExY1x1YjI5NCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzU0NFx1YjJjOFx1Yjc3YyBcdWMxMzggXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDFiNVx1ZDY1NFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVjODA0XHVkNjU0XHViOWRkXHVjNzQwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWM1ZWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1ZDFiNVx1ZDY1NFx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNWYwXHVhY2IwXHVkNTU4XHVjNWVjIFx1YzgwNFx1ZDY1NFx1YjlkZFx1YzVkMCBcdWM4MTFcdWMxOGRcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMyYTRcdWM3MDRcdWNlNThcdWI0ZTRcdWM3NDAgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzJlMFx1ZDYzOFx1Yjk3YyBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI5YzFcdWQwNmNcdWM1ZDAgXHVjNzU4XHVkNTU4XHVjNWVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyYTRcdWM3MDRcdWNlNThcdWI0ZTRcdWM3NDAgXHVjODA0XHVkNjU0XHViOWRkXHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YzVlYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM4MTFcdWMxOGRcdWQ1NWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWMyYTRcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNWYwXHVhY2IwXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWQ1NmRcdWMwYzEgXHVkMWI1XHVkNjU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzgwNFx1ZDY1NFx1YjlkZFx1YzVkMFx1YzExYyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViOWMxXHVkMDZjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMWI1XHVjMmUwXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjXHViMjk0IFx1Yzc3NFx1YjRlNCBcdWMxMzggXHVjMGFjXHViNzhjXHVjNzQ0IFx1YzgwNFx1ZDY1NFx1YjlkZFx1Yzc0NCBcdWQxYjVcdWQ1NThcdWM1ZWMgXHVjNWYwXHVhY2IwXHVkNTc0XHVjOGZjXHViMjk0XHViMzcwLCBcdWFjMDBcdWM3YTUgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YzgwMVx1YWM4YyBcdWI0MThcdWIzYzRcdWI4NWQgXHVjNWYwXHVhY2IwXHVkNTU4XHVhY2UwXHVjNzkwXHVkNTVjXHViMmU0LiBcdWMxMzggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzVmMFx1YWNiMFx1ZDU1YyBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc0NCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWI0MThcdWIzYzRcdWI4NWQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDNcL0JJTjAwMDEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MjcycHg7IHdpZHRoOjM4NXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4IG4oMSZsdDs9biZsdDs9MTAwMCkgXHViMjk0IFx1YzgwNFx1ZDY1NFx1YjlkZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4IG1cdWM3NDAgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNjQwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViOWMxXHVkMDZjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjJlOCwgXHVhYzE5XHVjNzQwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViOWMxXHVkMDZjXHViMjk0IDEgXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDEgXHVjMmE0XHVjNzA0XHVjZTU4XHViNGU0XHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViODVjIG4gXHViYzg4IFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjOThcdWM3NGNcdWM3NTggXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjljMVx1ZDA2Y1x1YzVkMCBcdWM3NThcdWQ1NThcdWM1ZWMgXHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1YjQ1MCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhZGY4IFx1YjljMVx1ZDA2Y1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IDEwMCBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjQgXHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IFx1YzEzOCBcdWJhODVcdWM3NTggXHVkMWI1XHVkNjU0XHVjNzkwXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YmE3MCwgXHVjMTM4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgM1x1Yzc5MCBcdWQxYjVcdWQ2NTRcdWI5N2MgXHVkNTU4XHViMjk0XHViMzcwIFx1Yzc4OFx1YzViNFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWQxYjVcdWQ2NTRcdWQ1NjAgXHViNTRjIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YzY0MCBcdWMxMzhcdWJhODVcdWM3NTggXHVkMWI1XHVkNjU0XHVjNzkwXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjMGMxXHVjNWQwXHVjMTFjXHVjNzU4IFx1YjljMVx1ZDA2Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWI5YzFcdWQwNmNcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7XHViZTQ0XHVjNmE5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzOTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25mZXJlbmNlIENhbGwiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdGVsZWNvbSBjb21wYW55IHdvdWxkIGxpa2UgdG8gb2ZmZXIgYSB0aHJlZS1wYXJ0eSBjb25mZXJlbmNlIGNhbGwgc2VydmljZS4gVGhpcyBzZXJ2aWNlIGVuYWJsZXMgdGhyZWUgY3VzdG9tZXJzIHRvIHBhcnRpY2lwYXRlIGluIGEgdGVsZXBob25lIGNvbnZlcnNhdGlvbiBzaW11bHRhbmVvdXNseS4gQSBjdXN0b21lciBhY2Nlc3NlcyB0aGUgaW50ZXJjb25uZWN0aW9uIG5ldHdvcmsgb2YgdGhlIHRlbGVwaG9uZSBzeXN0ZW0gdmlhIGEgc3dpdGNoLiBUaGUgbmV0d29yayBjb25zaXN0cyBvZiBzd2l0Y2hlcyBsaW5rZWQgYnkgYmlkaXJlY3Rpb25hbCBsaW5lcy4gT3ZlciB0aGUgZXhpc3RpbmcgbmV0d29yaywgdGhlIHRocmVlIHBhcnRpY2lwYW50cyBhY2Nlc3NpbmcgdGhlIG5ldHdvcmsgdmlhIHRocmVlIGRpZmZlcmVudCBzd2l0Y2hlcywgbXVzdCBiZSBjb25uZWN0ZWQgd2l0aCB0aGUgbWluaW11bSBjb3N0LiBOb3RlIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gY29ubmVjdCBhbnkgdHdvIHN3aXRjaGVzLiBZb3Ugd2lsbCBiZSBnaXZlbiBhbGwgdGhlIGxpbmtzIGJldHdlZW4gdGhlIHN3aXRjaGVzIG9mIHRoZSBuZXR3b3JrIGFsb25nIHdpdGggdGhlaXIgYXNzb2NpYXRlZCBjb3N0cy4gWW91IGFyZSByZXF1ZXN0ZWQgdG8gZmluZCB0aGUgY29ubmVjdGlvbnMgd2hpY2ggd2lsbCBtaW5pbWl6ZSB0aGUgdG90YWwgY29zdCBvZiBpbnRlcmNvbm5lY3RpbmcgdGhlIHRocmVlIHN3aXRjaGVzIHRvIHdoaWNoIHRoZSBwYXJ0aWNpcGFudHMgaW4gYSBjb25mZXJlbmNlIGNhbGwgYXJlIGNvbm5lY3RlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHRleHQgZmlsZSBuYW1lZCBjb25mLmlucC4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIG51bWJlcnMgOiBUaGUgbnVtYmVyIG9mIHN3aXRjaGVzLCBkZXNpZ25hdGVkIGJ5IChOICZsdDs9IDEwMDApIGFuZCB0aGUgbnVtYmVyIG9mIHN3aXRjaC10by1zd2l0Y2ggbGlua3MgaW4gdGhlIG5ldHdvcmssIGRlc2lnbmF0ZWQgYnkgRSwgc2VwYXJhdGVkIGJ5IGEgYmxhbmsuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBFIGlucHV0IGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzLCBkZXNpZ25hdGVkIGJ5IGksIGogYW5kIGM8c3ViPmksajxcL3N1Yj4gd2hlcmUgaSBhbmQgaiBhcmUgdGhlIG51bWJlcnMgb2YgdHdvIGRpZmZlcmVudCBzd2l0Y2hlcyBhbmQgY2ksamlzIHRoZSBjb3N0IG9mIHVzaW5nIHRoZSBsaW5rIGJldHdlZW4gaSBhbmQgaiBpbiBhIGNvbmZlcmVuY2UgY2FsbCAoMSAmbHQ7PSBjPHN1Yj5pLGo8XC9zdWI+Jmx0Oz0gMTAwKSwgZWFjaCBzZXBhcmF0ZWQgYnkgb25lIGJsYW5rLiBUaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzLCB3aGljaCBkZXNpZ25hdGUgdGhlIHRocmVlIHN3aXRjaGVzIHRoYXQgcGFydGljaXBhdGUgaW4gdGhlIGNvbmZlcmVuY2UgY2FsbCwgZWFjaCBzZXBhcmF0ZWQgYnkgb25lIGJsYW5rLiBUaGUgc3dpdGNoZXMgYXJlIGlkZW50aWZpZWQgd2l0aCBpbnRlZ2VycyAxIHRocm91Z2ggTiBjb25zZWN1dGl2ZWx5PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgbXVzdCBiZSBhIHRleHQgZmlsZSBuYW1lZCBjb25mLm91dC4gVGhlIGZpcnN0IGxpbmUgbXVzdCBjb250YWluIHRoZSB0b3RhbCAobWluaW1hbCkgY29zdCBvZiBlc3RhYmxpc2hpbmcgYSBjb25mZXJlbmNlIGNhbGwgYW1vbmcgdGhlIGdpdmVuIHRocmVlIHN3aXRjaGVzIGFuZCB0aGUgbnVtYmVyIFIgb2Ygc3dpdGNoLXRvLXN3aXRjaCBjb25uZWN0aW9ucyBuZWVkZWQgdG8gZXN0YWJsaXNoIHRoaXMgY29uZmVyZW5jZSBjYWxsLCBzZXBhcmF0ZWQgYnkgYSBibGFuay4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgbXVzdCBjb250YWluIHR3byBpbnRlZ2Vycywgd2hpY2ggZGVub3RlIHRoYXQgdGhlIGxpbmsgYmV0d2VlbiB0aGUgc3dpdGNoIG51bWJlcmVkIGJ5IHRoZSBmaXJzdCBpbnRlZ2VyIGFuZCB0aGUgc3dpdGNoIG51bWJlcmVkIGJ5IHRoZSBzZWNvbmQgaW50ZWdlciBpcyBpbmNsdWRlZCBpbiB0aGUgc29sdXRpb24gLW9yZGVyaW5nIG9mIGJldHdlZW4gdGhlIHR3byBzd2l0Y2hlcyBpcyBub3QgaW1wb3J0YW50LiBUaGUgb3JkZXJpbmcgYW1vbmcgdGhlIGxhc3QgUiBsaW5lcyBvZiB0aGUgb3V0cHV0IGlzIGFsc28gbm90IGltcG9ydGFudC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb25mLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjI3MnB4OyB3aWR0aDozODVweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Balkan Olympiad in Informatics > BOI 1998 4번