시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3581 668 330 22.759%

문제

농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.

두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최소값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.

  +---5---+---3---+    ->    +---3---+

게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.

주어진 파이프들의 맵으로부터 우물(A)와 외양관(Z) 사이의 유량을 결정하라.

각 노드의 이름은 알파벳으로 지어져 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

파이프 BC와 CD는 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

그러면 BD와 DZ 역시 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

병렬 연결된 BZ 역시 합쳐진다.

                 B
        A+---3---+---9---+Z

그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.

        A+---3---+Z

한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.

i번째 파이프는 두개의 다른 노드 ai와 bi와 연결돼 있고 Fi (1 ≤ Fi ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.

출력

첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.

예제 입력 1

5
A B 3
B C 3
C D 5
D Z 4
B Z 6

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjYwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVjNzIwXHViN2M5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWMwYWNcdWFmYmMgXHVjODc0XHVjNzQwIFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWNkYTlcdWJkODRcdWQ1NWMgXHViYjNjXHVjNzQ0IFx1YjljOFx1YzJkY1x1YWUzOCBcdWM2ZDBcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWIxOGRcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjNmIwXHViYjNjXHVjNWQwXHVjMTFjIFx1YzY3OFx1YzU5MVx1YWMwNFx1Yzc0NCBcdWM3ODdcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWM3NTggXHVjOWMwXHViM2M0XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1Yzg3NFx1Yzc0MCBcdWM1NDRcdWM4ZmMgXHViMmU0XHVjNTkxXHVkNTVjIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWI0ZTRcdWM3NzQgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YzZiMFx1YzVmMFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViM2ZjXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YzU0Y1x1YzU1OFx1YjJlNC4gXHVjODc0XHVjNzQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTQgXHVjNzIwXHViN2M5XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWM3NzQgXHVkNTVjXHVjOTA0XHViODVjIFx1YzVmMFx1YWNiMCBcdWIzZmMgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWI0NTAgXHVhZDAwXHVjNzU4IFx1YzcyMFx1YjdjOSBcdWM5MTEgXHVjZDVjXHVjMThjXHVhYzEyXHVjNzNjXHViODVjIFx1ZDc1MFx1Yjk3NFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNmE5XHViN2M5XHVjNzc0IDVcdWM3NzggXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIFx1YzZhOVx1YjdjOVx1Yzc3NCAzXHVjNzc4IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWJhNzQgXHVkNTVjXHVhYzFjXHVjNzU4IFx1YzZhOVx1YjdjOSAzXHVjOWRjXHViOWFjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgKy0tLTUtLS0rLS0tMy0tLSsgICAgLSZndDsgICAgKy0tLTMtLS0rPFwvcHJlPlxyXG5cclxuPHA+XHVhYzhjXHViMmU0XHVhYzAwLCBcdWJjZDFcdWI4MmNcdWI4NWMgXHVjNWYwXHVhY2IwXHViM2ZjIFx1Yzc4OFx1YjI5NCBcdWJjMzBcdWMyMThcdWFkMDBcdWI0ZTRcdWM3NDAgXHVhYzAxIFx1YzZhOVx1YjdjOVx1Yzc1OCBcdWQ1NjlcdWI5Y2NcdWQwN2NcdWM3NTggXHViYjNjXHVjNzQ0IFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgKy0tLTUtLS0rXHJcbiAtLS0rICAgICAgICstLS0gICAgLSZndDsgICAgKy0tLTgtLS0rXHJcbiAgICArLS0tMy0tLStcclxuPFwvcHJlPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWM1YjRcdWI1YTQgXHVhYzgzXHVjNWQwXHViM2M0IFx1YzVmMFx1YWNiMFx1YjNmYyBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWJiM2NcdWM3NDQgXHVkNzUwXHViOTc0XHVhYzhjIFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWJiYzBcdWI4NWMgXHVjODFjXHVhYzcwXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgKy0tLTUtLS0rXHJcbiAtLS0rICAgICAgICAgICAgICAgLSZndDsgICAgKy0tLTMtLS0rXHJcbiAgICArLS0tMy0tLSstLVxyXG48XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YmNmNVx1YzdhMVx1ZDU1OFx1YWM4YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYWE4XHViNGUwIFx1YmMzMFx1YzIxOFx1YWQwMFx1YjRlNFx1Yzc0MCBcdWQ1NWNcdWFjMWNcdWM3NTggXHVjZDVjXHViMzAwIFx1YzcyMFx1YjdjOVx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViYzMwXHVjMjE4XHVhZDAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjRlNFx1Yzc1OCBcdWI5ZjVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjNmIwXHViYjNjKEEpXHVjNjQwIFx1YzY3OFx1YzU5MVx1YWQwMChaKSBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNzIwXHViN2M5XHVjNzQ0IFx1YWNiMFx1YzgxNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1YzljMFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgKy0tLS0tLS0tLS0tNi0tLS0tLS0tLS0tK1xyXG4gICAgICAgIEErLS0tMy0tLStCICAgICAgICAgICAgICAgICAgICAgICtaXHJcbiAgICAgICAgICAgICAgICAgKy0tLTMtLS0rLS0tNS0tLSstLS00LS0tK1xyXG4gICAgICAgICAgICAgICAgICAgICAgICAgQyAgICAgICBEXHJcbjxcL3ByZT5cclxuXHJcbjxwPlx1ZDMwY1x1Yzc3NFx1ZDUwNCBCQ1x1YzY0MCBDRFx1YjI5NCBcdWQ1NjlcdWNjZDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS02LS0tLS0tLS0tLS0rXHJcbiAgICAgICAgQSstLS0zLS0tK0IgICAgICAgICAgICAgICAgICAgICAgK1pcclxuICAgICAgICAgICAgICAgICArLS0tLS0zLS0tLS0rLS0tLS00LS0tLS0rXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRFxyXG48XC9wcmU+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWJhNzQgQkRcdWM2NDAgRFogXHVjNWVkXHVjMmRjIFx1ZDU2OVx1Y2NkMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICstLS0tLS0tLS0tLTYtLS0tLS0tLS0tLStcclxuICAgICAgICBBKy0tLTMtLS0rQiAgICAgICAgICAgICAgICAgICAgICArWlxyXG4gICAgICAgICAgICAgICAgICstLS0tLS0tLS0tLTMtLS0tLS0tLS0tLStcclxuPFwvcHJlPlxyXG5cclxuPHA+XHViY2QxXHViODJjIFx1YzVmMFx1YWNiMFx1YjQxYyBCWiBcdWM1ZWRcdWMyZGMgXHVkNTY5XHVjY2QwXHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgIEJcclxuICAgICAgICBBKy0tLTMtLS0rLS0tOS0tLStaXHJcbjxcL3ByZT5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YmE3NCBBQlx1YzY0MCBCWiBcdWM1ZWRcdWMyZGMgXHVkNTY5XHVjY2QwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWFjZTAgXHVjNmE5XHViN2M5IDNcdWM3NzggXHViYzMwXHVjMjE4XHVhZDAwIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgQSstLS0zLS0tK1o8XC9wcmU+XHJcblxyXG48cD5cdWQ1NWMgXHVkMzBjXHVjNzc0XHVkNTA0XHViNGU0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWM3N2RcdWFjZTAuIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWM0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWIxOTNcdWM3NDAgXHViNGE0IEFcdWJkODBcdWQxMzAgWlx1YWU0Y1x1YzljMCBcdWQ3NTBcdWI5NzRcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzcyMFx1YjdjOVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWI3N2MuIFx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI0ZTRcdWM3NDAgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM4MDFcdWM2YTlcdWMyZGNcdWNmMWMgXHVjOTA0XHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVkMzBjXHVjNzc0XHVkNTA0XHViMjk0IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHViMTc4XHViNGRjIGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzVmMFx1YWNiMFx1YjNmYyBcdWM3ODhcdWFjZTAgRjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBGPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM3MjBcdWI3YzlcdWM3NDQgXHVhYzE2XHViMjk0XHViMmU0LiBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDAgXHVhYzE5XHVjOWMwXHViOWNjLCBcdWIzMDBcdWMxOGNcdWJiMzhcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNzUwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDcwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjgsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWM3NzRcdWI5ODQoXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MCBcdWI2MTBcdWIyOTQgXHVjMThjXHViYjM4XHVjNzkwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsJm5ic3A7XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YzZhOVx1YjdjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBXHVjNWQwXHVjMTFjIFpcdWFlNGNcdWM5YzBcdWM3NTggXHVjZDVjXHViMzAwIFx1YzcyMFx1YjdjOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjA4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvdGFsIEZsb3ciLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGFsd2F5cyB3YW50cyBoaXMgY293cyB0byBoYXZlIGVub3VnaCB3YXRlciBhbmQgdGh1cyBoYXMgbWFkZSBhIG1hcCBvZiB0aGUgTiAoMSAmbHQ7PSBOICZsdDs9IDcwMCkgd2F0ZXIgcGlwZXMgb24gdGhlIGZhcm0gdGhhdCBjb25uZWN0IHRoZSB3ZWxsIHRvIHRoZSBiYXJuLiBIZSB3YXMgc3VycHJpc2VkIHRvIGZpbmQgYSB3aWxkIG1lc3Mgb2YgZGlmZmVyZW50IHNpemUgcGlwZXMgY29ubmVjdGVkIGluIGFuIGFwcGFyZW50bHkgaGFwaGF6YXJkIHdheS4gSGUgd2FudHMgdG8gY2FsY3VsYXRlIHRoZSBmbG93IHRocm91Z2ggdGhlIHBpcGVzLjxcL3A+XHJcblxyXG48cD5Ud28gcGlwZXMgY29ubmVjdGVkIGluIGEgcm93IGFsbG93IHdhdGVyIGZsb3cgdGhhdCBpcyB0aGUgbWluaW11bSBvZiB0aGUgdmFsdWVzIG9mIHRoZSB0d28gcGlwZSYjMzk7cyBmbG93IHZhbHVlcy4gVGhlIGV4YW1wbGUgb2YgYSBwaXBlIHdpdGggZmxvdyBjYXBhY2l0eSA1IGNvbm5lY3RpbmcgdG8gYSBwaXBlIG9mIGZsb3cgY2FwYWNpdHkgMyBjYW4gYmUgcmVkdWNlZCBsb2dpY2FsbHkgdG8gYSBzaW5nbGUgcGlwZSBvZiBmbG93IGNhcGFjaXR5IDM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgKy0tLTUtLS0rLS0tMy0tLSsgICAgLSZndDsgICAgKy0tLTMtLS0rXHJcbjxcL3ByZT5cclxuXHJcbjxwPlNpbWlsYXJseSwgcGlwZXMgaW4gcGFyYWxsZWwgbGV0IHRocm91Z2ggd2F0ZXIgdGhhdCBpcyB0aGUgc3VtIG9mIHRoZWlyIGZsb3cgY2FwYWNpdGllczo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICstLS01LS0tK1xyXG4gLS0tKyAgICAgICArLS0tICAgIC0mZ3Q7ICAgICstLS04LS0tK1xyXG4gICAgKy0tLTMtLS0rXHJcbjxcL3ByZT5cclxuXHJcbjxwPkZpbmFsbHksIGEgcGlwZSB0aGF0IGNvbm5lY3RzIHRvIG5vdGhpbmcgZWxzZSBjYW4gYmUgcmVtb3ZlZDsgaXQgY29udHJpYnV0ZXMgbm8gZmxvdyB0byB0aGUgZmluYWwgb3ZlcmFsbCBjYXBhY2l0eTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICstLS01LS0tK1xyXG4gLS0tKyAgICAgICAgICAgICAgIC0mZ3Q7ICAgICstLS0zLS0tK1xyXG4gICAgKy0tLTMtLS0rLS1cclxuPFwvcHJlPlxyXG5cclxuPHA+QWxsIHRoZSBwaXBlcyBpbiB0aGUgbWFueSBtYXplcyBvZiBwbHVtYmluZyBjYW4gYmUgcmVkdWNlZCB1c2luZyB0aGVzZSBpZGVhcyBpbnRvIGEgc2luZ2xlIHRvdGFsIGZsb3cgY2FwYWNpdHkuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbWFwIG9mIHRoZSBwaXBlcywgZGV0ZXJtaW5lIHRoZSBmbG93IGNhcGFjaXR5IGJldHdlZW4gdGhlIHdlbGwgKEEpIGFuZCB0aGUgYmFybiAoWikuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoaXMgZXhhbXBsZSB3aGVyZSBub2RlIG5hbWVzIGFyZSBsYWJlbGVkIHdpdGggbGV0dGVyczo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS02LS0tLS0tLS0tLS0rXHJcbiAgICAgICAgQSstLS0zLS0tK0IgICAgICAgICAgICAgICAgICAgICAgK1pcclxuICAgICAgICAgICAgICAgICArLS0tMy0tLSstLS01LS0tKy0tLTQtLS0rXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICBDICAgICAgIERcclxuPFwvcHJlPlxyXG5cclxuPHA+UGlwZSBCQyBhbmQgQ0QgY2FuIGJlIGNvbWJpbmVkOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICstLS0tLS0tLS0tLTYtLS0tLS0tLS0tLStcclxuICAgICAgICBBKy0tLTMtLS0rQiAgICAgICAgICAgICAgICAgICAgICArWlxyXG4gICAgICAgICAgICAgICAgICstLS0tLTMtLS0tLSstLS0tLTQtLS0tLStcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICBEXHJcbjxcL3ByZT5cclxuXHJcbjxwPlRoZW4gQkQgYW5kIERaIGNhbiBiZSBjb21iaW5lZDo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS02LS0tLS0tLS0tLS0rXHJcbiAgICAgICAgQSstLS0zLS0tK0IgICAgICAgICAgICAgICAgICAgICAgK1pcclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS0zLS0tLS0tLS0tLS0rXHJcbjxcL3ByZT5cclxuXHJcbjxwPlRoZW4gdHdvIGxlZ3Mgb2YgQlogY2FuIGJlIGNvbWJpbmVkOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgIEJcclxuICAgICAgICBBKy0tLTMtLS0rLS0tOS0tLStaXHJcbjxcL3ByZT5cclxuXHJcbjxwPlRoZW4gQUIgYW5kIEJaIGNhbiBiZSBjb21iaW5lZCB0byB5aWVsZCBhIG5ldCBjYXBhY2l0eSBvZiAzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgIEErLS0tMy0tLStaXHJcbjxcL3ByZT5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byByZWFkIGluIGEgc2V0IG9mIHBpcGVzIGRlc2NyaWJlZCBhcyB0d28gZW5kcG9pbnRzIGFuZCB0aGVuIGNhbGN1bGF0ZSB0aGUgbmV0IGZsb3cgY2FwYWNpdHkgZnJvbSAmIzM5O0EmIzM5OyB0byAmIzM5O1omIzM5Oy4gQWxsIG5ldHdvcmtzIGluIHRoZSB0ZXN0IGRhdGEgY2FuIGJlIHJlZHVjZWQgdXNpbmcgdGhlIHJ1bGVzIGhlcmUuPFwvcD5cclxuXHJcbjxwPlBpcGUgaSBjb25uZWN0cyB0d28gZGlmZmVyZW50IG5vZGVzIGFfaSBhbmQgYl9pIChhX2kgaW4gcmFuZ2UgJiMzOTtBLVphLXomIzM5OzsgYl9pIGluIHJhbmdlICYjMzk7QS1aYS16JiMzOTspIGFuZCBoYXMgZmxvdyBGX2kgKDEgJmx0Oz0gRl9pICZsdDs9IDEsMDAwKS4gTm90ZSB0aGF0IGxvd2VyLSBhbmQgdXBwZXItY2FzZSBub2RlIG5hbWVzIGFyZSBpbnRlbmRlZCB0byBiZSB0cmVhdGVkIGFzIGRpZmZlcmVudC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4gKyAxOiBMaW5lIGkrMSBkZXNjcmliZXMgcGlwZSBpIHdpdGggdHdvIGxldHRlcnMgYW5kIGFuIGludGVnZXIsIGFsbCBzcGFjZS1zZXBhcmF0ZWQ6IGFfaSwgYl9pLCBhbmQgRl9pPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciB0aGF0IHRoZSBtYXhpbXVtIGZsb3cgZnJvbSB0aGUgd2VsbCAoJiMzOTtBJiMzOTspIHRvIHRoZSBiYXJuICgmIzM5O1omIzM5Oyk8XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO January 2009 Contest > Silver 2번