시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 12 2 2 22.222%

문제

숫자가 적혀져 있고, 순서가 있는 루트 있는 트리(Labeled and ordered rooted tree) 2개 T와 T'가 주어진다. 이 때, T와 T'사이의 거리를 구하는 프로그램을 작성하시오. 거리란 T를 T'와 동등하게 만드는 최소 연산의 횟수이다.

연산은 총 세가지로 이루어져 있다.

  1. T의 한 노드에 적혀있는 숫자를 바꾼다.
  2. T에서 루트가 아닌 노드를 하나 삭제한다.
  3. T의 루트 아래 어딘가에 노드를 하나 삽입한다.

T와 T'는 순서가 있는 트리이다. 따라서, 리프가 아닌 노드가 자식을 c개 가지고 있는 경우에 1부터 c까지 순서가 존재하며, 1번째 자식, 2번째 자식, ..., c번째 자식이 존재한다.

X와 Y가 동등한 트리가 되려면 X와 Y의 루트에 같은 숫자가 적혀있어야 하고, 같은 개수의 자식을 가져야 한다. 자식의 수를 c라고 했을 때, i번째 자식을 루트로하는 서브트리가 동등해야 한다. (i = 1, 2, ..., c)

T의 루트가 아닌 노드를 삽입하고 삭제하는 방법은 다음과 같다. 먼저, 루트가 아닌 노드 w가 자식을 d개 가지고 있고, w의 부모가 u이고, w가 u의 i번째 자식인 경우를 생각해보자. w를 삭제하게 되면, w의 첫번째 자식은 u의 i번째 자식이 되고, 두번째 자식은 u의 (i+1)번째 자식이 된다. j<i인 u의 j번째 자식의 순서는 그대로 유지되지만, j>i인 j번째 자식은 모두 u의 (j+d-1)번째 자식이 된다. w의 자식이 u의 자식으로 삽입되어서 오른쪽으로 밀려난다고 생각하면 된다.

루트가 아닌 노드 w를 삽입하려면, 먼저 w의 부모가 될 노드 u를 선택해야 한다. 그 다음, u의 자식 중에서 연속된 부분 수열을 골라서 w의 자식으로 만들어주고, 그 자리에 w를 삽입한다. 삽입과 동시에 w에는 적절한 숫자를 적을 수 있다.

T의 루트를 삭제하거나, 루트의 위에 새 노드를 삽입하는 것은 불가능하다. 루트에 적혀있는 숫자는 바꿀 수 있다.

w를 삭제하는 경우와 u의 2번째 자식부터 4번째 자식을 w의 자식으로 만들고 u 아래에 삽입하는 경우.

입력

첫째 줄에 T와 T'의 크기 n, m이 주어진다. (1 ≤ n, m ≤ 60) 다음 n개 줄에는 T의 정보가 주어진다. i번째 줄에는 i번째 노드의 정보가 주어진다. 노드에 적혀있는 숫자, 자식의 수가 주어지며, 그 다음에는 자식이 순서대로 주어진다. 다음 m개 줄에는 T'의 정보가 주어진다. 숫자는 항상 음이 아닌 정수이며, 각 트리의 루트 노드는 다른 노드의 자식으로 포함되지 않는 노드이다.

출력

T를 T'와 동등하게 만들기 위해 필요한 연산의 최소 횟수를 출력한다.

예제 입력 1

3 2
6 0
1 2 0 2
4 0
2 1 1
4 0

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijc2MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVjNzIwXHVjMGFjXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWI4ZThcdWQyYjggXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhYyhMYWJlbGVkIGFuZCBvcmRlcmVkIHJvb3RlZCB0cmVlKSAyXHVhYzFjIFRcdWM2NDAgVCYjMzk7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgVFx1YzY0MCBUJiMzOTtcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjNzBcdWI5YWNcdWI3ODAgVFx1Yjk3YyBUJiMzOTtcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1ZDY5Zlx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWYwXHVjMGIwXHVjNzQwIFx1Y2QxZCBcdWMxMzhcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UXHVjNzU4IFx1ZDU1YyBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlRcdWM1ZDBcdWMxMWMgXHViOGU4XHVkMmI4XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzBhZFx1YzgxY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+VFx1Yzc1OCBcdWI4ZThcdWQyYjggXHVjNTQ0XHViNzk4IFx1YzViNFx1YjUxOFx1YWMwMFx1YzVkMCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzBiZFx1Yzc4NVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UXHVjNjQwIFQmIzM5O1x1YjI5NCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWI5YWNcdWQ1MDRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWM3OTBcdWMyZGRcdWM3NDQgY1x1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCAxXHViZDgwXHVkMTMwIGNcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgMVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGQsIDJcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkLCAuLi4sIGNcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+WFx1YzY0MCBZXHVhYzAwIFx1YjNkOVx1YjRmMVx1ZDU1YyBcdWQyYjhcdWI5YWNcdWFjMDAgXHViNDE4XHViODI0XHViYTc0IFhcdWM2NDAgWVx1Yzc1OCBcdWI4ZThcdWQyYjhcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFjMTlcdWM3NDAgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjE4XHViOTdjIGNcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgaVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NDQgXHViOGU4XHVkMmI4XHViODVjXHVkNTU4XHViMjk0IFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YWMwMCBcdWIzZDlcdWI0ZjFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiAoaSA9IDEsIDIsIC4uLiwgYyk8XC9wPlxyXG5cclxuPHA+VFx1Yzc1OCBcdWI4ZThcdWQyYjhcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NThcdWFjZTAgXHVjMGFkXHVjODFjXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHViMTc4XHViNGRjIHdcdWFjMDAgXHVjNzkwXHVjMmRkXHVjNzQ0IGRcdWFjMWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgd1x1Yzc1OCBcdWJkODBcdWJhYThcdWFjMDAgdVx1Yzc3NFx1YWNlMCwgd1x1YWMwMCB1XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzc4IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuIHdcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgd1x1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzQwIHVcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWI0NTBcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzQwIHVcdWM3NTggKGkrMSlcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzc0IFx1YjQxY1x1YjJlNC4gaiZsdDtpXHVjNzc4IHVcdWM3NTggalx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YWRmOFx1YjMwMFx1Yjg1YyBcdWM3MjBcdWM5YzBcdWI0MThcdWM5YzBcdWI5Y2MsIGomZ3Q7aVx1Yzc3OCBqXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZFx1Yzc0MCBcdWJhYThcdWI0NTAgdVx1Yzc1OCAoaitkLTEpXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWI0MWNcdWIyZTQuIHdcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzc0IHVcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1YzBiZFx1Yzc4NVx1YjQxOFx1YzViNFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHViYzAwXHViODI0XHViMDljXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHViMTc4XHViNGRjIHdcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTU4XHViODI0XHViYTc0LCBcdWJhM2NcdWM4MDAgd1x1Yzc1OCBcdWJkODBcdWJhYThcdWFjMDAgXHViNDIwIFx1YjE3OFx1YjRkYyB1XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIHVcdWM3NTggXHVjNzkwXHVjMmRkIFx1YzkxMVx1YzVkMFx1YzExYyBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWFjZThcdWI3N2NcdWMxMWMgd1x1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOGZjXHVhY2UwLCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIHdcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTVjXHViMmU0LiBcdWMwYmRcdWM3ODVcdWFjZmMgXHViM2Q5XHVjMmRjXHVjNWQwIHdcdWM1ZDBcdWIyOTQgXHVjODAxXHVjODA4XHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VFx1Yzc1OCBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHVhYzcwXHViMDk4LCBcdWI4ZThcdWQyYjhcdWM3NTggXHVjNzA0XHVjNWQwIFx1YzBjOCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCZuYnNwO1x1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC4gXHViOGU4XHVkMmI4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZXNpbS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjhweDsgd2lkdGg6NTQzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+d1x1Yjk3YyBcdWMwYWRcdWM4MWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNjQwIHVcdWM3NTggMlx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWJkODBcdWQxMzAgNFx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NDQgd1x1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVhY2UwIHUgXHVjNTQ0XHViNzk4XHVjNWQwIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFRcdWM2NDAgVCYjMzk7XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuLCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuLCBtICZsZTsgNjApIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBUXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHViMTc4XHViNGRjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwLCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWM3OTBcdWMyZGRcdWM3NzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFQmIzM5O1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHViYTcwLCBcdWFjMDEgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHViMmU0XHViOTc4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVkM2VjXHVkNTY4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1Yjk3YyBUJiMzOTtcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHVhYzhjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NjE4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZSBTaW1pbGFyaXR5IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIHR3byBsYWJlbGVkIGFuZCBvcmRlcmVkIHJvb3RlZCB0cmVlcyBUIGFuZCBUJiMzOTsgYW5kIHdvdWxkIGxpa2UgdG8gY2FsY3VsYXRlIHRoZSBkaXN0YW5jZSBmcm9tIFQgdG8gVCYjMzk7LCB3aGljaCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyB5b3UgY2FuIHBlcmZvcm0gb24gVCB0byBtYWtlIGl0IGVxdWl2YWxlbnQgdG8gVCYjMzk7LiBGb3IgZWFjaCBvcGVyYXRpb24geW91IGNhbiBjaG9vc2UgdG8gZG8gb25lIG9mIHRocmVlIHRoaW5nczogKDEpIGNoYW5nZSB0aGUgbGFiZWwgb2Ygb25lIG5vZGUgaW4gVCwgKDIpIGRlbGV0ZSBhIG5vbi1yb290IG5vZGUgaW4gVCwgb3IgKDMpIGluc2VydCBhIG5ldyBub2RlIGluIFQgYXQgYSBwb3NpdGlvbiBzb21ld2hlcmUgYmVsb3cgaXRzIHJvb3QuIFJlY2FsbCB0aGUgdHJlZXMgVCBhbmQgVCYjMzk7IGFyZSBvcmRlcmVkLCB3aGljaCBtZWFucyB0aGF0IGlmIGEgbm9uLWxlYWYgbm9kZSBoYXMgYyBjaGlsZHJlbiwgaXRzIGNoaWxkcmVuIGFyZSBvcmRlcmVkIGZyb20gMSB0byBjLiBUaGF0IGlzLCB0aGVyZSBpcyBhIDFzdCBjaGlsZCwgYSAybmQgY2hpbGQsIGV0Yy4sIGFsbCB0aGUgd2F5IHVwIHRvIGEgY3RoIGNoaWxkLiBXaGVuIHdlIHNheSBhIHRyZWUgWCBpcyBlcXVpdmFsZW50IHRvIGEgdHJlZSBZICwgd2UgbWVhbiB0aGUgcm9vdCBvZiBYIHNob3VsZCBoYXZlIHRoZSBzYW1lIGxhYmVsIGFzIHRoZSByb290IG9mIFkgLCB0aGVpciByb290cyBzaG91bGQgaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2YgY2hpbGRyZW4gKGNhbGwgaXQgYyksIGFuZCB0aGUgc3VidHJlZSByb290ZWQgYXQgdGhlIGl0aCBjaGlsZCBvZiB0aGUgcm9vdCBvZiBYIHNob3VsZCBiZSBlcXVpdmFsZW50IHRvIHRoZSBzdWJ0cmVlIHJvb3RlZCBhdCB0aGUgaXRoIGNoaWxkIG9mIHRoZSByb290IG9mIFkgZm9yIGkgPSAxLCAyLCAuIC4gLiAsIGMuPFwvcD5cclxuXHJcbjxwPldlIG5vdyBkZXNjcmliZSB3aGF0IHdlIG1lYW4gYnkgZGVsZXRpb24gYW5kIGluc2VydGlvbiBvZiBub24tcm9vdCBub2RlcyBpbiBULiBXaGVuIGRlbGV0aW5nIGEgbm9uLXJvb3Qgbm9kZSB3IHdpdGggZCBjaGlsZHJlbiwgbGV0IHUgYmUgaXRzIHBhcmVudCBhbmQgc3VwcG9zZSB3IGlzIHUmcnNxdW87cyBpdGggY2hpbGQuIFRoZW4gdGhlIFx1ZmIwMXJzdCBjaGlsZCBvZiB3IGJlY29tZXMgdSZyc3F1bztzIGl0aCBjaGlsZCwgdGhlIHNlY29uZCBjaGlsZCBvZiB3IGJlY29tZXMgdSZyc3F1bztzIChpICsgMSlzdCBjaGlsZCwgZXRjLiBGb3IgaiAmbHQ7IGksIHRoZSBqdGggY2hpbGQgb2YgdSByZW1haW5zIHRoZSBzYW1lLCBidXQgZm9yIGFsbCBqICZndDsgaSwgdGhlIGNoaWxkIHdoaWNoIHdhcyBmb3JtZXJseSB0aGUganRoIGNoaWxkIG9mIHUgbm93IGJlY29tZXMgaXRzIChqK2QmbWludXM7MSlzdCBjaGlsZCAodGhleSBnZXQgJmxkcXVvO3NoaWZ0ZWQgb3ZlciZyZHF1bzsgZHVlIHRvIHRoZSBpbnNlcnRpb24gb2YgdyZyc3F1bztzIGNoaWxkcmVuIGludG8gdSZyc3F1bztzIGNoaWxkIGxpc3QpLiBUbyBpbnNlcnQgYSBub24tcm9vdCBub2RlIHcgaW50byB0aGUgdHJlZSwgd2UgY2FuIGNob29zZSBhbnkgbm9kZSB1IHRvIGJlIGl0cyBwYXJlbnQsIGFuZCB3ZSBjYW4gY2hvb3NlIGFueSBjb250aWd1b3VzIHN1YnNlcXVlbmNlIChwb3NzaWJseSBlbXB0eSkgb2YgdSZyc3F1bztzIGNoaWxkcmVuIHRvIGJlY29tZSB3JnJzcXVvO3MgY2hpbGRyZW4sIHB1dHRpbmcgdyBpbiB0aGVpciBwbGFjZS4gV2hlbiBpbnNlcnRpbmcgYSBub2RlLCB3ZSBjYW4gZ2l2ZSBpdCBhbnkgbGFiZWwgd2Ugd2FudCBhdCB0aGUgdGltZSBvZiBpbnNlcnRpb24uIFRoZSByb290IG9mIFQgY2FuIG5ldmVyIGJlIGRlbGV0ZWQsIGFuZCB5b3UgY2FuIG5ldmVyIGluc2VydCBhIG5ldyBub2RlIGFib3ZlIHRoZSByb290IHRvIGJlY29tZSB0aGUgb2xkIHJvb3QmcnNxdW87cyBwYXJlbnQuIFlvdSBjYW4sIGhvd2V2ZXIsIGNoYW5nZSB0aGUgbGFiZWwgb2YgdGhlIHJvb3QuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZXNpbS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjhweDsgd2lkdGg6NTQzcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBuIGFuZCBtIHNlcGFyYXRlZCBieSBhIHNwYWNlLCB0aGUgc2l6ZXMgb2YgdGhlIHRyZWVzIFQgYW5kIFQmIzM5OywgcmVzcGVjdGl2ZWx5ICgxICZsZTsgbiwgbSAmbGU7IDYwKS4gVGhlIG5leHQgbiBsaW5lcyBkZXNjcmliZSBULiBPbiB0aGUgaXRoIGxpbmUgaXMgYSBkZXNjcmlwdGlvbiBvZiB0aGUgaXRoIG5vZGUgaW4gdGhlIHRyZWU6IGl0cyBsYWJlbCwgdGhlIG51bWJlciBvZiBjaGlsZHJlbiBpdCBoYXMsIHRoZW4gYSBsaXN0IG9mIGl0cyBjaGlsZHJlbiBpbiBvcmRlciBmcm9tIFx1ZmIwMXJzdCB0byBsYXN0LCBhbGwgc3BhY2Utc2VwYXJhdGVkLiBUaGUgbmV4dCBtIGxpbmVzIHNpbWlsYXJseSBkZXNjcmliZSBUJiMzOTsuIExhYmVscyBhcmUgYWx3YXlzIG5vbm5lZ2F0aXZlIGludGVnZXJzLiBUaGUgcm9vdCBvZiBlYWNoIHRyZWUgaXMgdGhlIG5vZGUgd2hpY2ggaXMgbm90IHRoZSBjaGlsZCBvZiBhbnkgb3RoZXIgbm9kZSBpbiB0aGUgdHJlZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiBhIHNpbmdsZSBsaW5lIG91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyB0aGF0IGNhbiBiZSBwZXJmb3JtZWQgb24gVCB0byBtYWtlIGl0IGVxdWl2YWxlbnQgdG8gVCYjMzk7LCBmb2xsb3dlZCBieSBhIG5ld2xpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Individual Round 2008 6번