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

문제

코리아 통신회사에서는 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+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4IG4oMSAmbGU7IG4gJmxlOyAxMDAwKSBcdWIyOTQgXHVjODA0XHVkNjU0XHViOWRkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMTggbVx1Yzc0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWM2NDAgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI5YzFcdWQwNmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViMmU4LCBcdWFjMTlcdWM3NDAgXHVjMmE0XHVjNzA0XHVjZTU4XHViNGU0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI5YzFcdWQwNmNcdWIyOTQgMSBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWMwMSBcdWMyYTRcdWM3MDRcdWNlNThcdWI0ZTRcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWI4NWMgbiBcdWJjODggXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkODBcdWM1ZWNcdWI0MWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCwgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1Yzc1OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViOWMxXHVkMDZjXHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YzVlYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWIyOTQgXHViNDUwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFkZjggXHViOWMxXHVkMDZjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgMTAwIFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNCBcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjMTM4IFx1YmE4NVx1Yzc1OCBcdWQxYjVcdWQ2NTRcdWM3OTBcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNTggXHViYzg4XHVkNjM4XHVjNzc0XHViYTcwLCBcdWMxMzggXHVjODE1XHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCAzXHVjNzkwIFx1ZDFiNVx1ZDY1NFx1Yjk3YyBcdWQ1NThcdWIyOTRcdWIzNzAgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHViZTQ0XHVjNmE5XHVjNzNjXHViODVjIFx1ZDFiNVx1ZDY1NFx1ZDU2MCBcdWI1NGMgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHVjNjQwIFx1YzEzOFx1YmE4NVx1Yzc1OCBcdWQxYjVcdWQ2NTRcdWM3OTBcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWMwYzFcdWM1ZDBcdWMxMWNcdWM3NTggXHViOWMxXHVkMDZjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjljMVx1ZDA2Y1x1YzVkMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWJlNDRcdWM2YTlcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjM5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbmZlcmVuY2UgQ2FsbCIsImRlc2NyaXB0aW9uIjoiPHA+QSB0ZWxlY29tIGNvbXBhbnkgd291bGQgbGlrZSB0byBvZmZlciBhIHRocmVlLXBhcnR5IGNvbmZlcmVuY2UgY2FsbCBzZXJ2aWNlLiBUaGlzIHNlcnZpY2UgZW5hYmxlcyB0aHJlZSBjdXN0b21lcnMgdG8gcGFydGljaXBhdGUgaW4gYSB0ZWxlcGhvbmUgY29udmVyc2F0aW9uIHNpbXVsdGFuZW91c2x5LiBBIGN1c3RvbWVyIGFjY2Vzc2VzIHRoZSBpbnRlcmNvbm5lY3Rpb24gbmV0d29yayBvZiB0aGUgdGVsZXBob25lIHN5c3RlbSB2aWEgYSBzd2l0Y2guIFRoZSBuZXR3b3JrIGNvbnNpc3RzIG9mIHN3aXRjaGVzIGxpbmtlZCBieSBiaWRpcmVjdGlvbmFsIGxpbmVzLiBPdmVyIHRoZSBleGlzdGluZyBuZXR3b3JrLCB0aGUgdGhyZWUgcGFydGljaXBhbnRzIGFjY2Vzc2luZyB0aGUgbmV0d29yayB2aWEgdGhyZWUgZGlmZmVyZW50IHN3aXRjaGVzLCBtdXN0IGJlIGNvbm5lY3RlZCB3aXRoIHRoZSBtaW5pbXVtIGNvc3QuIE5vdGUgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBjb25uZWN0IGFueSB0d28gc3dpdGNoZXMuIFlvdSB3aWxsIGJlIGdpdmVuIGFsbCB0aGUgbGlua3MgYmV0d2VlbiB0aGUgc3dpdGNoZXMgb2YgdGhlIG5ldHdvcmsgYWxvbmcgd2l0aCB0aGVpciBhc3NvY2lhdGVkIGNvc3RzLiBZb3UgYXJlIHJlcXVlc3RlZCB0byBmaW5kIHRoZSBjb25uZWN0aW9ucyB3aGljaCB3aWxsIG1pbmltaXplIHRoZSB0b3RhbCBjb3N0IG9mIGludGVyY29ubmVjdGluZyB0aGUgdGhyZWUgc3dpdGNoZXMgdG8gd2hpY2ggdGhlIHBhcnRpY2lwYW50cyBpbiBhIGNvbmZlcmVuY2UgY2FsbCBhcmUgY29ubmVjdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgdGV4dCBmaWxlIG5hbWVkIGNvbmYuaW5wLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gbnVtYmVycyA6IFRoZSBudW1iZXIgb2Ygc3dpdGNoZXMsIGRlc2lnbmF0ZWQgYnkgKE4gJmx0Oz0gMTAwMCkgYW5kIHRoZSBudW1iZXIgb2Ygc3dpdGNoLXRvLXN3aXRjaCBsaW5rcyBpbiB0aGUgbmV0d29yaywgZGVzaWduYXRlZCBieSBFLCBzZXBhcmF0ZWQgYnkgYSBibGFuay4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIEUgaW5wdXQgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIGRlc2lnbmF0ZWQgYnkgaSwgaiBhbmQgYzxzdWI+aSxqPFwvc3ViPiB3aGVyZSBpIGFuZCBqIGFyZSB0aGUgbnVtYmVycyBvZiB0d28gZGlmZmVyZW50IHN3aXRjaGVzIGFuZCBjaSxqaXMgdGhlIGNvc3Qgb2YgdXNpbmcgdGhlIGxpbmsgYmV0d2VlbiBpIGFuZCBqIGluIGEgY29uZmVyZW5jZSBjYWxsICgxICZsdDs9IGM8c3ViPmksajxcL3N1Yj4mbHQ7PSAxMDApLCBlYWNoIHNlcGFyYXRlZCBieSBvbmUgYmxhbmsuIFRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIHdoaWNoIGRlc2lnbmF0ZSB0aGUgdGhyZWUgc3dpdGNoZXMgdGhhdCBwYXJ0aWNpcGF0ZSBpbiB0aGUgY29uZmVyZW5jZSBjYWxsLCBlYWNoIHNlcGFyYXRlZCBieSBvbmUgYmxhbmsuIFRoZSBzd2l0Y2hlcyBhcmUgaWRlbnRpZmllZCB3aXRoIGludGVnZXJzIDEgdGhyb3VnaCBOIGNvbnNlY3V0aXZlbHk8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBtdXN0IGJlIGEgdGV4dCBmaWxlIG5hbWVkIGNvbmYub3V0LiBUaGUgZmlyc3QgbGluZSBtdXN0IGNvbnRhaW4gdGhlIHRvdGFsIChtaW5pbWFsKSBjb3N0IG9mIGVzdGFibGlzaGluZyBhIGNvbmZlcmVuY2UgY2FsbCBhbW9uZyB0aGUgZ2l2ZW4gdGhyZWUgc3dpdGNoZXMgYW5kIHRoZSBudW1iZXIgUiBvZiBzd2l0Y2gtdG8tc3dpdGNoIGNvbm5lY3Rpb25zIG5lZWRlZCB0byBlc3RhYmxpc2ggdGhpcyBjb25mZXJlbmNlIGNhbGwsIHNlcGFyYXRlZCBieSBhIGJsYW5rLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiBsaW5lcyBtdXN0IGNvbnRhaW4gdHdvIGludGVnZXJzLCB3aGljaCBkZW5vdGUgdGhhdCB0aGUgbGluayBiZXR3ZWVuIHRoZSBzd2l0Y2ggbnVtYmVyZWQgYnkgdGhlIGZpcnN0IGludGVnZXIgYW5kIHRoZSBzd2l0Y2ggbnVtYmVyZWQgYnkgdGhlIHNlY29uZCBpbnRlZ2VyIGlzIGluY2x1ZGVkIGluIHRoZSBzb2x1dGlvbiAtb3JkZXJpbmcgb2YgYmV0d2VlbiB0aGUgdHdvIHN3aXRjaGVzIGlzIG5vdCBpbXBvcnRhbnQuIFRoZSBvcmRlcmluZyBhbW9uZyB0aGUgbGFzdCBSIGxpbmVzIG9mIHRoZSBvdXRwdXQgaXMgYWxzbyBub3QgaW1wb3J0YW50LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NvbmYuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MjcycHg7IHdpZHRoOjM4NXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Balkan Olympiad in Informatics > BOI 1998 4번