시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6Ijc2MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVjNzIwXHVjMGFjXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWI4ZThcdWQyYjggXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhYyhMYWJlbGVkIGFuZCBvcmRlcmVkIHJvb3RlZCB0cmVlKSAyXHVhYzFjIFRcdWM2NDAgVCYjMzk7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBUXHVjNjQwIFQmIzM5O1x1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWM3MFx1YjlhY1x1Yjc4MCBUXHViOTdjIFQmIzM5O1x1YzY0MCBcdWIzZDlcdWI0ZjFcdWQ1NThcdWFjOGMgXHViOWNjXHViNGRjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVkNjlmXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZjBcdWMwYjBcdWM3NDAgXHVjZDFkIFx1YzEzOFx1YWMwMFx1YzljMFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRcdWM3NTggXHVkNTVjIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+VFx1YzVkMFx1YzExYyBcdWI4ZThcdWQyYjhcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWQ1NThcdWIwOTggXHVjMGFkXHVjODFjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5UXHVjNzU4IFx1YjhlOFx1ZDJiOCBcdWM1NDRcdWI3OTggXHVjNWI0XHViNTE4XHVhYzAwXHVjNWQwIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWQ1NThcdWIwOTggXHVjMGJkXHVjNzg1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlRcdWM2NDAgVCYjMzk7XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjlhY1x1ZDUwNFx1YWMwMCBcdWM1NDRcdWIyY2MgXHViMTc4XHViNGRjXHVhYzAwIFx1Yzc5MFx1YzJkZFx1Yzc0NCBjXHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwIDFcdWJkODBcdWQxMzAgY1x1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwLCAxXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZCwgMlx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGQsIC4uLiwgY1x1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5YXHVjNjQwIFlcdWFjMDAgXHViM2Q5XHViNGYxXHVkNTVjIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWI0MThcdWI4MjRcdWJhNzQgWFx1YzY0MCBZXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YzVkMCBcdWFjMTlcdWM3NDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWMxOVx1Yzc0MCBcdWFjMWNcdWMyMThcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc5MFx1YzJkZFx1Yzc1OCBcdWMyMThcdWI5N2MgY1x1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBpXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWI4ZThcdWQyYjhcdWI4NWNcdWQ1NThcdWIyOTQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVhYzAwIFx1YjNkOVx1YjRmMVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChpID0gMSwgMiwgLi4uLCBjKTxcL3A+XHJcblxyXG48cD5UXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHViMTc4XHViNGRjXHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YWNlMCBcdWMwYWRcdWM4MWNcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1YmEzY1x1YzgwMCwgXHViOGU4XHVkMmI4XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWIxNzhcdWI0ZGMgd1x1YWMwMCBcdWM3OTBcdWMyZGRcdWM3NDQgZFx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCB3XHVjNzU4IFx1YmQ4MFx1YmFhOFx1YWMwMCB1XHVjNzc0XHVhY2UwLCB3XHVhYzAwIHVcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gd1x1Yjk3YyBcdWMwYWRcdWM4MWNcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCB3XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzQwIHVcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZFx1Yzc0MCB1XHVjNzU4IChpKzEpXHViYzg4XHVjOWY4IFx1Yzc5MFx1YzJkZFx1Yzc3NCBcdWI0MWNcdWIyZTQuIGombHQ7aVx1Yzc3OCB1XHVjNzU4IGpcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjNzIwXHVjOWMwXHViNDE4XHVjOWMwXHViOWNjLCBqJmd0O2lcdWM3Nzggalx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NDAgXHViYWE4XHViNDUwIHVcdWM3NTggKGorZC0xKVx1YmM4OFx1YzlmOCBcdWM3OTBcdWMyZGRcdWM3NzQgXHViNDFjXHViMmU0LiB3XHVjNzU4IFx1Yzc5MFx1YzJkZFx1Yzc3NCB1XHVjNzU4IFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWMwYmRcdWM3ODVcdWI0MThcdWM1YjRcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YmMwMFx1YjgyNFx1YjA5Y1x1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4ZThcdWQyYjhcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjE3OFx1YjRkYyB3XHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YjgyNFx1YmE3NCwgXHViYTNjXHVjODAwIHdcdWM3NTggXHViZDgwXHViYWE4XHVhYzAwIFx1YjQyMCBcdWIxNzhcdWI0ZGMgdVx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCB1XHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjNWYwXHVjMThkXHViNDFjIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhY2U4XHViNzdjXHVjMTFjIHdcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzhmY1x1YWNlMCwgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCB3XHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1Y1x1YjJlNC4gXHVjMGJkXHVjNzg1XHVhY2ZjIFx1YjNkOVx1YzJkY1x1YzVkMCB3XHVjNWQwXHViMjk0IFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODAxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlRcdWM3NTggXHViOGU4XHVkMmI4XHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU1OFx1YWM3MFx1YjA5OCwgXHViOGU4XHVkMmI4XHVjNzU4IFx1YzcwNFx1YzVkMCBcdWMwYzggXHViMTc4XHViNGRjXHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAmbmJzcDtcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YjhlOFx1ZDJiOFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyZWVzaW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI4cHg7IHdpZHRoOjU0M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPndcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzY0MCB1XHVjNzU4IDJcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHViZDgwXHVkMTMwIDRcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzQ0IHdcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YWNlMCB1IFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWMwYmRcdWM3ODVcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBUXHVjNjQwIFQmIzM5O1x1Yzc1OCBcdWQwNmNcdWFlMzAgbiwgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiwgbSAmbGU7IDYwKSBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MCwgXHVjNzkwXHVjMmRkXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjMmRkXHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBUJiMzOTtcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVhYzAxIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4ZThcdWQyYjggXHViMTc4XHViNGRjXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHViMTc4XHViNGRjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRcdWI5N2MgVCYjMzk7XHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzYxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyZWUgU2ltaWxhcml0eSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiB0d28gbGFiZWxlZCBhbmQgb3JkZXJlZCByb290ZWQgdHJlZXMgVCBhbmQgVCYjMzk7IGFuZCB3b3VsZCBsaWtlIHRvIGNhbGN1bGF0ZSB0aGUgZGlzdGFuY2UgZnJvbSBUIHRvIFQmIzM5Oywgd2hpY2ggaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgeW91IGNhbiBwZXJmb3JtIG9uIFQgdG8gbWFrZSBpdCBlcXVpdmFsZW50IHRvIFQmIzM5Oy4gRm9yIGVhY2ggb3BlcmF0aW9uIHlvdSBjYW4gY2hvb3NlIHRvIGRvIG9uZSBvZiB0aHJlZSB0aGluZ3M6ICgxKSBjaGFuZ2UgdGhlIGxhYmVsIG9mIG9uZSBub2RlIGluIFQsICgyKSBkZWxldGUgYSBub24tcm9vdCBub2RlIGluIFQsIG9yICgzKSBpbnNlcnQgYSBuZXcgbm9kZSBpbiBUIGF0IGEgcG9zaXRpb24gc29tZXdoZXJlIGJlbG93IGl0cyByb290LiBSZWNhbGwgdGhlIHRyZWVzIFQgYW5kIFQmIzM5OyBhcmUgb3JkZXJlZCwgd2hpY2ggbWVhbnMgdGhhdCBpZiBhIG5vbi1sZWFmIG5vZGUgaGFzIGMgY2hpbGRyZW4sIGl0cyBjaGlsZHJlbiBhcmUgb3JkZXJlZCBmcm9tIDEgdG8gYy4gVGhhdCBpcywgdGhlcmUgaXMgYSAxc3QgY2hpbGQsIGEgMm5kIGNoaWxkLCBldGMuLCBhbGwgdGhlIHdheSB1cCB0byBhIGN0aCBjaGlsZC4gV2hlbiB3ZSBzYXkgYSB0cmVlIFggaXMgZXF1aXZhbGVudCB0byBhIHRyZWUgWSAsIHdlIG1lYW4gdGhlIHJvb3Qgb2YgWCBzaG91bGQgaGF2ZSB0aGUgc2FtZSBsYWJlbCBhcyB0aGUgcm9vdCBvZiBZICwgdGhlaXIgcm9vdHMgc2hvdWxkIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIGNoaWxkcmVuIChjYWxsIGl0IGMpLCBhbmQgdGhlIHN1YnRyZWUgcm9vdGVkIGF0IHRoZSBpdGggY2hpbGQgb2YgdGhlIHJvb3Qgb2YgWCBzaG91bGQgYmUgZXF1aXZhbGVudCB0byB0aGUgc3VidHJlZSByb290ZWQgYXQgdGhlIGl0aCBjaGlsZCBvZiB0aGUgcm9vdCBvZiBZIGZvciBpID0gMSwgMiwgLiAuIC4gLCBjLjxcL3A+XHJcblxyXG48cD5XZSBub3cgZGVzY3JpYmUgd2hhdCB3ZSBtZWFuIGJ5IGRlbGV0aW9uIGFuZCBpbnNlcnRpb24gb2Ygbm9uLXJvb3Qgbm9kZXMgaW4gVC4gV2hlbiBkZWxldGluZyBhIG5vbi1yb290IG5vZGUgdyB3aXRoIGQgY2hpbGRyZW4sIGxldCB1IGJlIGl0cyBwYXJlbnQgYW5kIHN1cHBvc2UgdyBpcyB1JnJzcXVvO3MgaXRoIGNoaWxkLiBUaGVuIHRoZSBcdWZiMDFyc3QgY2hpbGQgb2YgdyBiZWNvbWVzIHUmcnNxdW87cyBpdGggY2hpbGQsIHRoZSBzZWNvbmQgY2hpbGQgb2YgdyBiZWNvbWVzIHUmcnNxdW87cyAoaSArIDEpc3QgY2hpbGQsIGV0Yy4gRm9yIGogJmx0OyBpLCB0aGUganRoIGNoaWxkIG9mIHUgcmVtYWlucyB0aGUgc2FtZSwgYnV0IGZvciBhbGwgaiAmZ3Q7IGksIHRoZSBjaGlsZCB3aGljaCB3YXMgZm9ybWVybHkgdGhlIGp0aCBjaGlsZCBvZiB1IG5vdyBiZWNvbWVzIGl0cyAoaitkJm1pbnVzOzEpc3QgY2hpbGQgKHRoZXkgZ2V0ICZsZHF1bztzaGlmdGVkIG92ZXImcmRxdW87IGR1ZSB0byB0aGUgaW5zZXJ0aW9uIG9mIHcmcnNxdW87cyBjaGlsZHJlbiBpbnRvIHUmcnNxdW87cyBjaGlsZCBsaXN0KS4gVG8gaW5zZXJ0IGEgbm9uLXJvb3Qgbm9kZSB3IGludG8gdGhlIHRyZWUsIHdlIGNhbiBjaG9vc2UgYW55IG5vZGUgdSB0byBiZSBpdHMgcGFyZW50LCBhbmQgd2UgY2FuIGNob29zZSBhbnkgY29udGlndW91cyBzdWJzZXF1ZW5jZSAocG9zc2libHkgZW1wdHkpIG9mIHUmcnNxdW87cyBjaGlsZHJlbiB0byBiZWNvbWUgdyZyc3F1bztzIGNoaWxkcmVuLCBwdXR0aW5nIHcgaW4gdGhlaXIgcGxhY2UuIFdoZW4gaW5zZXJ0aW5nIGEgbm9kZSwgd2UgY2FuIGdpdmUgaXQgYW55IGxhYmVsIHdlIHdhbnQgYXQgdGhlIHRpbWUgb2YgaW5zZXJ0aW9uLiBUaGUgcm9vdCBvZiBUIGNhbiBuZXZlciBiZSBkZWxldGVkLCBhbmQgeW91IGNhbiBuZXZlciBpbnNlcnQgYSBuZXcgbm9kZSBhYm92ZSB0aGUgcm9vdCB0byBiZWNvbWUgdGhlIG9sZCByb290JnJzcXVvO3MgcGFyZW50LiBZb3UgY2FuLCBob3dldmVyLCBjaGFuZ2UgdGhlIGxhYmVsIG9mIHRoZSByb290LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyZWVzaW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI4cHg7IHdpZHRoOjU0M3B4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgbiBhbmQgbSBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgdGhlIHNpemVzIG9mIHRoZSB0cmVlcyBUIGFuZCBUJiMzOTssIHJlc3BlY3RpdmVseSAoMSAmbGU7IG4sIG0gJmxlOyA2MCkuIFRoZSBuZXh0IG4gbGluZXMgZGVzY3JpYmUgVC4gT24gdGhlIGl0aCBsaW5lIGlzIGEgZGVzY3JpcHRpb24gb2YgdGhlIGl0aCBub2RlIGluIHRoZSB0cmVlOiBpdHMgbGFiZWwsIHRoZSBudW1iZXIgb2YgY2hpbGRyZW4gaXQgaGFzLCB0aGVuIGEgbGlzdCBvZiBpdHMgY2hpbGRyZW4gaW4gb3JkZXIgZnJvbSBcdWZiMDFyc3QgdG8gbGFzdCwgYWxsIHNwYWNlLXNlcGFyYXRlZC4gVGhlIG5leHQgbSBsaW5lcyBzaW1pbGFybHkgZGVzY3JpYmUgVCYjMzk7LiBMYWJlbHMgYXJlIGFsd2F5cyBub25uZWdhdGl2ZSBpbnRlZ2Vycy4gVGhlIHJvb3Qgb2YgZWFjaCB0cmVlIGlzIHRoZSBub2RlIHdoaWNoIGlzIG5vdCB0aGUgY2hpbGQgb2YgYW55IG90aGVyIG5vZGUgaW4gdGhlIHRyZWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gYSBzaW5nbGUgbGluZSBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgdGhhdCBjYW4gYmUgcGVyZm9ybWVkIG9uIFQgdG8gbWFrZSBpdCBlcXVpdmFsZW50IHRvIFQmIzM5OywgZm9sbG93ZWQgYnkgYSBuZXdsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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