시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 11 6 6 54.545%

문제

창영 왕국의 왕 김상근은 왕국의 위대함을 널리 알리기 위해서 거대한 성을 건축하려고 한다. 성은 빌딩이 서로 연결된 형태이고, 빌딩은 홀과 홀을 연결하는 복도로 이루어져 있다.

처음에 성은 빌딩 하나로만 이루어져 있다. 이 빌딩은 메인 빌딩이라고 한다. 왕국의 인구가 증가할 때마다, 성은 다음과 같은 과정으로 확장된다.

새로운 부속 빌딩이 지어지면, 그 건물은 기존에 있던 빌딩과 연결된다. 새로 지어진 빌딩도 다른 빌딩과 마찬가지로 홀과 복도로 이루어져 있다. 또, 기존 건물의 홀과 새 건물의 홀을 연결하기 위해 새로운 복도를 만들어야 한다. 이 복도는 새 건물로 가는 유일한 통로이다.

한 빌딩에 있을 수 있는 홀의 최대 개수는 10개이다.

그림 1. 예제로 주어지는 성을 그림으로 나타낸 것.

요즘 상근이를 암살하려는 세력이 점점 커지고 있다. 상근이는 모든 홀에 전략적으로 경비원을 배치해서 모든 복도를 감시하게 하려고 한다. 상근이는 개인 경호원을 최대한 많이 데리고 있기를 원하기 때문에, 홀에 배치하는 경비원의 수는 최소로 하려고 한다. 얼마전에 성에 발생한 불로 인해서, 모든 홀과 복도 사이에는 문이 없다. 따라서, 경비원은 홀과 연결된 모든 복도를 감시할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 모든 홀는 1부터 10000까지의 숫자중 하나로 구분할 수 있다. 각 성은 재귀적으로 정의되어 있으며, 메인 빌딩부터 입력으로 주어진다.

테스트 케이스의 첫째 줄에는 메인 빌딩을 구성하고 있는 홀의 수 n (2 ≤ n ≤ 10), 복도의 수 m (1 ≤ m ≤ 45), 빌딩과 연결된 빌딩의 수 w (0 ≤ w ≤ 10)가 주어진다.

다음 줄부터 m개 줄에는 복도의 정보가 주어지며, 복도가 연결하는 홀의 번호가 주어진다. 두 홀은 항상 같은 빌딩안에 있다.

다음 w개 줄에는 다른 빌딩과 연결하는 복도의 정보가 주어진다. 복도의 정보는 두 숫자로 이루어져 있고, 현재 빌딩의 홀의 번호와 연결된 빌딩의 홀의 번호가 주어진다. 각 복도의 정보가 주어진 다음에는 연결된 빌딩의 정보가 메인 빌딩의 정보와 같은 형식으로 주어진다. (재귀적으로 주어지는 것이다. 빌딩의 정보가 주어진 후에는 다음에 연결된 빌딩의 정보가 주어지는 것이다. 마찬가지로, 연결된 빌딩의 정보가 주어지다가, 다시 그 건물과 연결된 빌딩의 정보가 주어지는 것이다. 즉, 성은 트리 구조라고 생각하면 된다)

성은 항상 모두 연결되어 있다. 즉, 각 홀은 다른 홀과 직접 또는 다른 홀을 통해서 연결되어져 있다. 같은 홀을 연결하는 복도(연결하는 홀의 번호가 같은 복도)는 존재하지 않으며, 두 홀 사이에 있을 수 있는 복도의 수는 최대 한 개이다.

출력

각각의 테스트 케이스에 대해서, 모든 복도를 감시하는데 필요한 경비원의 수의 최솟값을 출력한다.

예제 입력 1

5 8 2
1 2
2 4
3 4
1 3
1 5
2 5
3 5
4 5
1 6
3 3 0
6 7
7 8
8 6
5 10
3 2 2
10 11
10 12
11 13
2 1 0
13 9
11 14
3 2 0
14 15
14 16

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjM2NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYmRcdWJlNDRcdWM2ZDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMSBcdWM2NTVcdWFkNmRcdWM3NTggXHVjNjU1IFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc0MCBcdWM2NTVcdWFkNmRcdWM3NTggXHVjNzA0XHViMzAwXHVkNTY4XHVjNzQ0IFx1YjExMFx1YjlhYyBcdWM1NGNcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWM3MFx1YjMwMFx1ZDU1YyBcdWMxMzFcdWM3NDQgXHVhYzc0XHVjZDk1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMTMxXHVjNzQwIFx1YmU0Y1x1YjUyOVx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YWNlMCwgXHViZTRjXHViNTI5XHVjNzQwIFx1ZDY0MFx1YWNmYyBcdWQ2NDBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmNmNVx1YjNjNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjOThcdWM3NGNcdWM1ZDAgXHVjMTMxXHVjNzQwIFx1YmU0Y1x1YjUyOSBcdWQ1NThcdWIwOThcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmU0Y1x1YjUyOVx1Yzc0MCBcdWJhNTRcdWM3NzggXHViZTRjXHViNTI5XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNjU1XHVhZDZkXHVjNzU4IFx1Yzc3OFx1YWQ2Y1x1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWMxMzFcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgXHVkNjU1XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzhcdWI4NWNcdWM2YjQgXHViZDgwXHVjMThkIFx1YmU0Y1x1YjUyOVx1Yzc3NCBcdWM5YzBcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YWRmOCBcdWFjNzRcdWJiM2NcdWM3NDAgXHVhZTMwXHVjODc0XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWJlNGNcdWI1MjlcdWFjZmMgXHVjNWYwXHVhY2IwXHViNDFjXHViMmU0LiBcdWMwYzhcdWI4NWMgXHVjOWMwXHVjNWI0XHVjOWM0IFx1YmU0Y1x1YjUyOVx1YjNjNCBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVhY2ZjIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBcdWQ2NDBcdWFjZmMgXHViY2Y1XHViM2M0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVhZTMwXHVjODc0IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWQ2NDBcdWFjZmMgXHVjMGM4IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWQ2NDBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViY2Y1XHViM2M0XHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWJjZjVcdWIzYzRcdWIyOTQgXHVjMGM4IFx1YWM3NFx1YmIzY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1ZDFiNVx1Yjg1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YmU0Y1x1YjUyOVx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ2NDBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YjI5NCAxMFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jYXN0bGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IHdpZHRoOjUwNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxLiBcdWM2MDhcdWM4MWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzEzMVx1Yzc0NCBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4My48XC9wPlxyXG5cclxuPHA+XHVjNjk0XHVjOTk4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM1NTRcdWMwYjRcdWQ1NThcdWI4MjRcdWIyOTQgXHVjMTM4XHViODI1XHVjNzc0IFx1YzgxMFx1YzgxMCBcdWNlZTRcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDY0MFx1YzVkMCBcdWM4MDRcdWI3YjVcdWM4MDFcdWM3M2NcdWI4NWMgXHVhY2JkXHViZTQ0XHVjNmQwXHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHViY2Y1XHViM2M0XHViOTdjIFx1YWMxMFx1YzJkY1x1ZDU1OFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzFjXHVjNzc4IFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1YjM3MFx1YjlhY1x1YWNlMCBcdWM3ODhcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVkNjQwXHVjNWQwIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWJlNDRcdWM2ZDBcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM1YmNcdWI5YzhcdWM4MDRcdWM1ZDAgXHVjMTMxXHVjNWQwIFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWJkODhcdWI4NWMgXHVjNzc4XHVkNTc0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVkNjQwXHVhY2ZjIFx1YmNmNVx1YjNjNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzc0IFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjYmRcdWJlNDRcdWM2ZDBcdWM3NDAgXHVkNjQwXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJhYThcdWI0ZTAgXHViY2Y1XHViM2M0XHViOTdjIFx1YWMxMFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVkNjQwXHViMjk0IDFcdWJkODBcdWQxMzAgMTAwMDBcdWFlNGNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzEzMVx1Yzc0MCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViYTU0XHVjNzc4IFx1YmU0Y1x1YjUyOVx1YmQ4MFx1ZDEzMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYTU0XHVjNzc4IFx1YmU0Y1x1YjUyOVx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1ZDY0MFx1Yzc1OCBcdWMyMTggbiAoMiAmbGU7IG4gJmxlOyAxMCksIFx1YmNmNVx1YjNjNFx1Yzc1OCBcdWMyMTggbSAoMSAmbGU7IG0gJmxlOyA0NSksIFx1YmU0Y1x1YjUyOVx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViZTRjXHViNTI5XHVjNzU4IFx1YzIxOCB3ICgwICZsZTsgdyAmbGU7IDEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViY2Y1XHViM2M0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmNmNVx1YjNjNFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkNjQwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWQ2NDBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWMxOVx1Yzc0MCBcdWJlNGNcdWI1MjlcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgd1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHViOTc4IFx1YmU0Y1x1YjUyOVx1YWNmYyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViY2Y1XHViM2M0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmNmNVx1YjNjNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViNDUwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWQ2MDRcdWM3YWMgXHViZTRjXHViNTI5XHVjNzU4IFx1ZDY0MFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWQ2NDBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmNmNVx1YjNjNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViZTRjXHViNTI5XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWJhNTRcdWM3NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzgxNVx1YmNmNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFx1YzdhY1x1YWRjMFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJlNGNcdWI1MjlcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJlNGNcdWI1MjlcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YywgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMmU0XHVhYzAwLCBcdWIyZTRcdWMyZGMgXHVhZGY4IFx1YWM3NFx1YmIzY1x1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViZTRjXHViNTI5XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YzEzMVx1Yzc0MCBcdWQyYjhcdWI5YWMgXHVhZDZjXHVjODcwXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzEzMVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViYWE4XHViNDUwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1ZDY0MFx1Yzc0MCBcdWIyZTRcdWI5NzggXHVkNjQwXHVhY2ZjIFx1YzljMVx1YzgxMSBcdWI2MTBcdWIyOTQgXHViMmU0XHViOTc4IFx1ZDY0MFx1Yzc0NCBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1ZDY0MFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViY2Y1XHViM2M0KFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQ2NDBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWJjZjVcdWIzYzQpXHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YjQ1MCBcdWQ2NDAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmNmNVx1YjNjNFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHViY2Y1XHViM2M0XHViOTdjIFx1YWMxMFx1YzJkY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhY2JkXHViZTQ0XHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHdWFyZHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSByb3lhbCBjYXN0bGVzIGluIE1vbHZhbmlhIGZvbGxvdyB0aGUgZGVzaWduIG9mIGtpbmcgU2FuZSwgXHVmYjAxcnN0IG9mIGhpcyBkeW5hc3R5LiBIZSBydWxlZCBieSBkaXZpZGUgYW5kIGNvbnF1ZXIuIFRoZXJlZm9yZSwgYWxsIGNhc3RsZXMgYXJlIGJ1aWx0IGFjY29yZGluZyB0byBhIGhpZXJhcmNoaWNhbCBwYXR0ZXJuIGJhc2VkIG9uIGludGVyY29ubmVjdGVkIGJ1aWxkaW5ncy4gQSBidWlsZGluZyBjb25zaXN0cyBvZiBoYWxscyBhbmQgY29ycmlkb3JzIHRoYXQgY29ubmVjdCBoYWxscy48XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5LCBhIGNhc3RsZSBjb25zaXN0cyBvZiBvbmx5IG9uZSBidWlsZGluZyAodGhlIG1haW4gYnVpbGRpbmcpLiBXaGVuIGl0cyBwb3B1bGF0aW9uIGdyb3dzLCB0aGUgY2FzdGxlIGlzIGV4dGVuZGVkIGFzIGZvbGxvd3M6IEEgbmV3IHBlcmlwaGVyYWwgYnVpbGRpbmcgaXMgY29uc3RydWN0ZWQsIGF0dGFjaGVkIHRvIG9uZSBvZiB0aGUgZXhpc3RpbmcgYnVpbGRpbmdzLiBMaWtlIGFueSBvdGhlciBidWlsZGluZywgdGhlIG5ldyBidWlsZGluZyBhbHNvIGNvbnNpc3RzIG9mIGhhbGxzIGFuZCBjb3JyaWRvcnMuIEFuIGFkZGl0aW9uYWwgY29ycmlkb3IgaXMgY3JlYXRlZCB0byBjb25uZWN0IGEgaGFsbCBpbiB0aGUgZXhpc3RpbmcgYnVpbGRpbmcgdG8gYSBoYWxsIGluIHRoZSBuZXcgYnVpbGRpbmcuIFRoYXQgY29ycmlkb3IgaXMgdGhlIG9ubHkgd2F5IHRvIGFjY2VzcyB0aGUgbmV3IGJ1aWxkaW5nLjxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVyIG9mIGhhbGxzIGluIGEgYnVpbGRpbmcgaXMgYXQgbW9zdCAxMC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jYXN0bGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IHdpZHRoOjUwNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBUaGUgY2FzdGxlIGxheW91dCBvZiB0aGUgZXhhbXBsZSBwcm92aWRlZCBiZWxvdy48XC9wPlxyXG5cclxuPHA+SW4gdGltZXMgb2YgdHVybW9pbCwgdGhlIGtpbmcgbW9uaXRvcnMgYWxsIGNvcnJpZG9ycyBieSBzdHJhdGVnaWNhbGx5IHBsYWNpbmcgZ3VhcmRzIGluIGhhbGxzLiBIZSBhc2tzIHlvdSB0byBkZXRlcm1pbmUgdGhlIGxlYXN0IG51bWJlciBvZiBndWFyZHMgcmVxdWlyZWQgdG8gbW9uaXRvciBhbGwgY29ycmlkb3JzIGluIHRoZSBjYXN0bGUgKGFzIGhlIHdhbnRzIHRvIGtlZXAgaGlzIHBlcnNvbmFsIGd1YXJkIGFzIGxhcmdlIGFzIHBvc3NpYmxlKS4gTm90ZSB0aGF0IHNpbmNlIHRoZSBsYXN0IFx1ZmIwMXJlLCB0aGVyZSBhcmUgbm8gZG9vcnMgaW4gdGhlIGNhc3RsZSwgc28gd2UgY2FuIHNhZmVseSBhc3N1bWUgdGhhdCBhIGd1YXJkIHBsYWNlZCBpbiBhIGhhbGwgY2FuIG1vbml0b3IgYWxsIGNvbm5lY3RpbmcgY29ycmlkb3JzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgbnVtYmVyIG9mIGNhc3RsZSBkZXNjcmlwdGlvbnMuIFdpdGhpbiBhIGNhc3RsZSwgZWFjaCBoYWxsIGlzIGlkZW50aVx1ZmIwMWVkIGJ5IGEgdW5pcXVlIG51bWJlciBiZXR3ZWVuIDEgYW5kIDEwMDAwLiBFYWNoIGNhc3RsZSBpcyByZWN1cnNpdmVseSBkZVx1ZmIwMW5lZCwgc3RhcnRpbmcgd2l0aCBhIGRlc2NyaXB0aW9uIG9mIHRoZSBtYWluIGJ1aWxkaW5nOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkEgbGluZSBjb250YWluaW5nIHRocmVlIGludGVnZXJzLCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBoYWxscyBpbiB0aGlzIGJ1aWxkaW5nICgyICZsZTsgbiAmbGU7IDEwKSwgdGhlIG51bWJlciBvZiBjb3JyaWRvcnMgaW4gdGhpcyBidWlsZGluZyAoMSAmbGU7IG0gJmxlOyA0NSksIGFuZCB0aGUgbnVtYmVyIG9mIHBlcmlwaGVyYWwgYnVpbGRpbmdzIHRoYXQgd2VyZSBsYXRlciBhdHRhY2hlZCB0byB0aGlzIGJ1aWxkaW5nICgwICZsZTsgdyAmbGU7IDEwKS48XC9saT5cclxuXHQ8bGk+Rm9yIGVhY2ggb2YgdGhlIG0gY29ycmlkb3JzOlxyXG5cdDx1bD5cclxuXHRcdDxsaT5BIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgKGVhY2ggJmxlOyAxMDAwMCksIHJlcHJlc2VudGluZyB0aGUgdHdvIGhhbGxzIGNvbm5lY3RlZCBieSB0aGlzIGNvcnJpZG9yLiBCb3RoIGhhbGxzIGFyZSBsb2NhdGVkIGluc2lkZSB0aGUgY3VycmVudCBidWlsZGluZy48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+Rm9yIGVhY2ggb2YgdGhlIHcgcGVyaXBoZXJhbCBidWlsZGluZ3M6XHJcblx0PHVsPlxyXG5cdFx0PGxpPkEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycywgZGVzY3JpYmluZyB0aGUgY29ycmlkb3IgdGhhdCBsZWFkcyB0byB0aGlzIHBlcmlwaGVyYWwgYnVpbGRpbmcuIFRoZSBcdWZiMDFyc3QgaW50ZWdlciByZXByZXNlbnRzIGEgaGFsbCBpbiB0aGUgY3VycmVudCBidWlsZGluZywgd2hpbGUgdGhlIHNlY29uZCBpbnRlZ2VyIHJlcHJlc2VudHMgYSBoYWxsIGluIHRoZSBwZXJpcGhlcmFsIGJ1aWxkaW5nLjxcL2xpPlxyXG5cdFx0PGxpPlRoZSBzdHJ1Y3R1cmUgb2YgdGhlIHBlcmlwaGVyYWwgYnVpbGRpbmcgYW5kIGFueSBuZXdlciBidWlsZGluZ3MgdGhhdCB3ZXJlIGxhdGVyIGF0dGFjaGVkIHRvIGl0LCBkZXNjcmliZWQgYnkgcmVwZWF0aW5nIHJ1bGVzIDEgdG8gMy48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgY2FzdGxlIGlzIGZ1bGx5IGNvbm5lY3RlZDogYW55IGhhbGwgaXMgZGlyZWN0bHkgb3IgaW5kaXJlY3RseSByZWFjaGFibGUgZnJvbSBhbnkgb3RoZXIgaGFsbC4gQ29ycmlkb3JzIHdpdGggdGhlIHNhbWUgc3RhcnQgYW5kIGVuZCBoYWxsIGRvIG5vdCBleGlzdCwgYW5kIGZvciBldmVyeSB0d28gaGFsbHMgdGhlcmUgaXMgYXQgbW9zdCBvbmUgY29ycmlkb3IgYmV0d2VlbiB0aGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc3RsZSwgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG1pbmltdW0gbnVtYmVyIG9mIGd1YXJkcyB0byBwbGFjZSBpbiBoYWxscyBzdWNoIHRoYXQgYWxsIGNvcnJpZG9ycyBpbiB0aGUgY2FzdGxlIGFyZSBtb25pdG9yZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 G번

  • 문제의 오타를 찾은 사람: arine
  • 문제를 번역한 사람: baekjoon