시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 31 8 7 53.846%

문제

  어떤 나라에는 커다란 담장이 여러 개 건설되어, 한 담장의 양 끝은 정확히 두 마을과 연결이 돼 있다. 이 문제에서 마을은 점으로, 담장은 마을을 연결하는 선으로 표현된다. 담끼리 교차하는 경우는 없다. 그래서 이 나라는 담장 때문에 국토가 여러 "구역"으로 나눠지게 되는데, 한 구역에서 다른 구역으로 가려면 마을을 통과하거나 담을 넘어야 한다. 각 담장들은 모두 서로 이어져 있기 때문에 임의의 마을 A와 B에 대해서 한쪽 끝이 A이거나 B인 담장이 반드시 존재하며, 고립돼 있는 마을이 없다. 또한 담장만 따라 걸어가면 A에서 B까지 갈 수 있다.
  이들 마을에 사는 사람들을 대상으로 하는 모임이 하나 있다. 각 마을마다 최대 한 명이 모임에 가입해 있으며, 모임에 가입한 사람이 한 명도 없는 마을도 있다. 그런데, 모임에 든 사람들이 마을 바깥에 있는 한 구역에서 만나고 싶어한다. 여기 회원들은 자전거를 타고 그 약속장소로 가는데, 교통 문제 때문에 마을을 통과하지 않으려 한다. 그리고 가는 과정에서 담장은 가능한 한 적게 넘고 싶다. 이들은, 도착하기 위해 각 회원들이 담장을 넘어야 하는 횟수의 합이 가장 적게 되는 곳을 찾아 거기서 모이기를 원한다.

  마을은 1부터 N까지 번호가 매겨져 있다. (N은 마을의 총 개수) 그림 1을 보면, 정점은 마을을 나타내고, 정점들을 잇는 선은 담장을 나타낸다. 그리고 모임에 든 사람은 3번, 6번, 9번 마을에 한 사람씩 있다고 가정하자. 이때, 이 사람들이 전체적으로 담장을 가장 적게 거쳐서 모일 수 있는 적합한 곳은 그림 2에 나타나 있는 구역이다. 각 마을 사람이 화살표 친 대로 이동하면 되는 것이다. 담장을 넘은 총횟수는 2이다. 6번 사람이 4번과 7번 마을 사이에 있는 담을 넘어야 하고, 9번 사람이 2번과 4번 마을 사이에 있는 담을 넘었기 때문이다.

  마을과 담장, 그리고 모임에 속한 사람들에 대한 자료를 입력받아, 모이기에 가장 적합한 구역을 고르고 담장을 넘는 총횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

  첫째 줄에는 구역의 개수 M이있다(2<=M<= 200). (그림 1을 살펴보면 생겨난 다각형 개수가 경계 바깥을 포함해서 10개임을 알 수 있다. 그 개수를 일컫는다.) 둘째 줄에는 마을(그림에서 꼭짓점)의개수N이있다(2<=N<= 250). 셋째 줄에는 모임에 든 회원의수L이들어있다(1<=L<=30, L<=N). 그리고 넷째 줄에는 각 회원이 사는 마을의 번호를 나타내는 L개의 정수가 오름차순으로 들어있다.

  그리고 다음에는 2M개의 줄이 있으며, 한 구역에 대한 정보가 두 줄에 걸쳐 들어있다. 거기서 첫줄에는 이 구역이 감싸는 마을의 개수 I가 들어있으며, 다음줄에는 이 구역의 경계를 이루는 마을 I개의 번호가 시계 방향 순서로 들어있다. 다만, 한 가지 예외가 있는데, 가장 마지막에 있는 구역은(M째 구역) 마을 전체의 바깥을 이루는 구역에 대한 정보이다. 이 구역을 다룰 때만은 가장 바깥을 감싸고 있는 마을들의 번호가 반시계 방향 순서로 제시된다. 이렇듯 입력 파일에는 담과 마을로 인해 생겨난 모든 구역에 대한 정보가 바깥쪽 구역까지 포함해서 모두 들어있다.

  구역은 입력 파일에 수록돼 있는 순서가 곧 그 구역을 지정하는 번호가 된다. 가장 먼저 나오는 구역이 1번 구역, 그 다음에 있는 구역이 2번이다. 즉, 모이기에 가장 적합한 구역을 가리킬 때는 입력 파일에서 몇째로 나온 구역인지를 출력하면 된다.

출력

  첫째 줄에는 답안 프로그램이 구한 총횟수의 최솟값을 출력한다. 둘째 줄에는 담장을 가장 적게 넘고 만날 수 있는 구역의 번호를 출력한다. 그런 구역이 여러 개 있을 수 있더라도 한 곳만 출력하면 된다.

예제 입력 1

10
10
3
3 6 9 
3
1 2 3 
3
1 3 7 
4
2 4 7 3 
3
4 6 7 
3
4 8 6 
3
6 8 7 
3
4 5 8 
4
7 8 10 9 
3
5 10 8 
7
7 9 10 5 4 2 1

예제 출력 1

2
3
W3sicHJvYmxlbV9pZCI6IjIzNjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZjRcdWM3YTUgXHViMTA4XHViYTM4XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQmbmJzcDsgXHVjNWI0XHViNWE0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBcdWNlZTRcdWIyZTRcdWI3ODAgXHViMmY0XHVjN2E1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVhYzc0XHVjMTI0XHViNDE4XHVjNWI0LCBcdWQ1NWMgXHViMmY0XHVjN2E1XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM3NDAgXHVjODE1XHVkNjU1XHVkNzg4IFx1YjQ1MCBcdWI5YzhcdWM3NDRcdWFjZmMgXHVjNWYwXHVhY2IwXHVjNzc0IFx1YjNmYyBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHViOWM4XHVjNzQ0XHVjNzQwIFx1YzgxMFx1YzczY1x1Yjg1YywgXHViMmY0XHVjN2E1XHVjNzQwIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC4gXHViMmY0XHViMDdjXHViOWFjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1YjI5NCBcdWIyZjRcdWM3YTUgXHViNTRjXHViYjM4XHVjNWQwIFx1YWQ2ZFx1ZDFhMFx1YWMwMCBcdWM1ZWNcdWI3ZWMgJnF1b3Q7XHVhZDZjXHVjNWVkJnF1b3Q7XHVjNzNjXHViODVjIFx1YjA5OFx1YjIyMFx1YzljMFx1YWM4YyBcdWI0MThcdWIyOTRcdWIzNzAsIFx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWI4MjRcdWJhNzQgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YWM3MFx1YjA5OCBcdWIyZjRcdWM3NDQgXHViMTE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YjJmNFx1YzdhNVx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjIFx1Yzc3NFx1YzViNFx1YzgzOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWI5YzhcdWM3NDQgQVx1YzY0MCBCXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWNcdWNhYmQgXHViMDVkXHVjNzc0IEFcdWM3NzRcdWFjNzBcdWIwOTggQlx1Yzc3OCBcdWIyZjRcdWM3YTVcdWM3NzQgXHViYzE4XHViNGRjXHVjMmRjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgXHVhY2UwXHViOWJkXHViM2ZjIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViMmY0XHVjN2E1XHViOWNjIFx1YjUzMFx1Yjc3YyBcdWFjNzhcdWM1YjRcdWFjMDBcdWJhNzQgQVx1YzVkMFx1YzExYyBCXHVhZTRjXHVjOWMwIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LjxiciBcLz5cclxuXHQmbmJzcDsgXHVjNzc0XHViNGU0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYWNcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YjMwMFx1YzBjMVx1YzczY1x1Yjg1YyBcdWQ1NThcdWIyOTQgXHViYWE4XHVjNzg0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWI5YzhcdWM3NDRcdWI5YzhcdWIyZTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJhODVcdWM3NzQgXHViYWE4XHVjNzg0XHVjNWQwIFx1YWMwMFx1Yzc4NVx1ZDU3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWFjMDBcdWM3ODVcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDU1YyBcdWJhODVcdWIzYzQgXHVjNWM2XHViMjk0IFx1YjljOFx1Yzc0NFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCwgXHViYWE4XHVjNzg0XHVjNWQwIFx1YjRlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViOWM4XHVjNzQ0IFx1YmMxNFx1YWU2NVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzAgXHVkNjhjXHVjNmQwXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzgwNFx1YWM3MFx1Yjk3YyBcdWQwYzBcdWFjZTAgXHVhZGY4IFx1YzU3ZFx1YzE4ZFx1YzdhNVx1YzE4Y1x1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAsIFx1YWQ1MFx1ZDFiNSBcdWJiMzhcdWM4MWMgXHViNTRjXHViYjM4XHVjNWQwIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHViMmY0XHVjN2E1XHVjNzQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjODAxXHVhYzhjIFx1YjExOFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Yzc3NFx1YjRlNFx1Yzc0MCwgXHViM2M0XHVjYzI5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHVkNjhjXHVjNmQwXHViNGU0XHVjNzc0IFx1YjJmNFx1YzdhNVx1Yzc0NCBcdWIxMThcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWI0MThcdWIyOTQgXHVhY2YzXHVjNzQ0IFx1Y2MzZVx1YzU0NCBcdWFjNzBcdWFlMzBcdWMxMWMgXHViYWE4XHVjNzc0XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIGhlaWdodD1cIjE5OVwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTAzXC93dy5wbmdcIiB3aWR0aD1cIjQ5NVwiIFwvPjxcL3A+XHJcbjxwPlxyXG5cdCZuYnNwOyBcdWI5YzhcdWM3NDRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiAoTlx1Yzc0MCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOCkgXHVhZGY4XHViOWJjIDFcdWM3NDQgXHViY2Y0XHViYTc0LCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHVjODE1XHVjODEwXHViNGU0XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWMxMjBcdWM3NDAgXHViMmY0XHVjN2E1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIDNcdWJjODgsIDZcdWJjODgsIDlcdWJjODggXHViOWM4XHVjNzQ0XHVjNWQwIFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM1MjkgXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzgwNFx1Y2NiNFx1YzgwMVx1YzczY1x1Yjg1YyBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWFjNzBcdWNjZDBcdWMxMWMgXHViYWE4XHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODAxXHVkNTY5XHVkNTVjIFx1YWNmM1x1Yzc0MCBcdWFkZjhcdWI5YmMgMlx1YzVkMCBcdWIwOThcdWQwYzBcdWIwOTggXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YjljOFx1Yzc0NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNjU0XHVjMGI0XHVkNDVjIFx1Y2U1YyBcdWIzMDBcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0IFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJmNFx1YzdhNVx1Yzc0NCBcdWIxMThcdWM3NDAgXHVjZDFkXHVkNjlmXHVjMjE4XHViMjk0IDJcdWM3NzRcdWIyZTQuIDZcdWJjODggXHVjMGFjXHViNzhjXHVjNzc0IDRcdWJjODhcdWFjZmMgN1x1YmM4OCBcdWI5YzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZjRcdWM3NDQgXHViMTE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgOVx1YmM4OCBcdWMwYWNcdWI3OGNcdWM3NzQgMlx1YmM4OFx1YWNmYyA0XHViYzg4IFx1YjljOFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjJmNFx1Yzc0NCBcdWIxMThcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdCZuYnNwOyBcdWI5YzhcdWM3NDRcdWFjZmMgXHViMmY0XHVjN2E1LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHVjNzg0XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Yzc5MFx1YjhjY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDQsIFx1YmFhOFx1Yzc3NFx1YWUzMFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVkNTY5XHVkNTVjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWFjZTAmbmJzcDtcdWIyZjRcdWM3YTVcdWM3NDQgXHViMTE4XHViMjk0IFx1Y2QxZFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHQmbmJzcDsgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzRcdWM3ODhcdWIyZTQoMiZsdDs9TSZsdDs9IDIwMCkuIChcdWFkZjhcdWI5YmMgMVx1Yzc0NCBcdWMwYjRcdWQzYjRcdWJjZjRcdWJhNzQgXHVjMGRkXHVhY2E4XHViMDljIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWFjMWNcdWMyMThcdWFjMDAgXHVhY2JkXHVhY2M0IFx1YmMxNFx1YWU2NVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NzRcdWMxMWMgMTBcdWFjMWNcdWM3ODRcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNzdjXHVjZWViXHViMjk0XHViMmU0LikgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM3NDQoXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YWYyZFx1YzlkM1x1YzgxMClcdWM3NThcdWFjMWNcdWMyMThOXHVjNzc0XHVjNzg4XHViMmU0KDImbHQ7PU4mbHQ7PSAyNTApLiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWI0ZTAgXHVkNjhjXHVjNmQwXHVjNzU4XHVjMjE4TFx1Yzc3NFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNCgxJmx0Oz1MJmx0Oz0zMCwgTCZsdDs9TikuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIxMzdcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ2OGNcdWM2ZDBcdWM3NzQgXHVjMGFjXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IExcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0Jm5ic3A7IFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgMk1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVhYzcwXHVhZTMwXHVjMTFjIFx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzQgXHVhZDZjXHVjNWVkXHVjNzc0IFx1YWMxMFx1YzJmOFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHVhYzFjXHVjMjE4IElcdWFjMDAgXHViNGU0XHVjNWI0XHVjNzg4XHVjNzNjXHViYTcwLCBcdWIyZTRcdWM3NGNcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjljOFx1Yzc0NCBJXHVhYzFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YjljYywgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWM2MDhcdWM2NzhcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NDAoTVx1YzlmOCBcdWFkNmNcdWM1ZWQpIFx1YjljOFx1Yzc0NCBcdWM4MDRcdWNjYjRcdWM3NTggXHViYzE0XHVhZTY1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIyZTRcdWI4ZjAgXHViNTRjXHViOWNjXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWJjMTRcdWFlNjVcdWM3NDQgXHVhYzEwXHVjMmY4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTUgXHVjMjFjXHVjMTFjXHViODVjIFx1YzgxY1x1YzJkY1x1YjQxY1x1YjJlNC4gXHVjNzc0XHViODA3XHViNGVmIFx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM1ZDBcdWIyOTQgXHViMmY0XHVhY2ZjIFx1YjljOFx1Yzc0NFx1Yjg1YyBcdWM3NzhcdWQ1NzQgXHVjMGRkXHVhY2E4XHViMDljIFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWJjMTRcdWFlNjVcdWNhYmQgXHVhZDZjXHVjNWVkXHVhZTRjXHVjOWMwIFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyBcdWJhYThcdWI0NTAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdCZuYnNwOyBcdWFkNmNcdWM1ZWRcdWM3NDAgXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1YzVkMCBcdWMyMThcdWI4NWRcdWIzZmMgXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWFjZTcgXHVhZGY4IFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWM5YzBcdWM4MTVcdWQ1NThcdWIyOTQgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCBcdWIwOThcdWM2MjRcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzc0IDFcdWJjODggXHVhZDZjXHVjNWVkLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NzQgMlx1YmM4OFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWJhYThcdWM3NzRcdWFlMzBcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1ZDU2OVx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM3NDQgXHVhYzAwXHViOWFjXHVkMGFjIFx1YjU0Y1x1YjI5NCBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjXHVjNWQwXHVjMTFjIFx1YmE4N1x1YzlmOFx1Yjg1YyBcdWIwOThcdWM2MjggXHVhZDZjXHVjNWVkXHVjNzc4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0Jm5ic3A7Jm5ic3A7XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjVcdWM1NDggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWQ2Y1x1ZDU1YyBcdWNkMWRcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWIxMThcdWFjZTAgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWFkNmNcdWM1ZWRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1NWMgXHVhY2YzXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldhbGxzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGNvdW50cnksIGdyZWF0IHdhbGxzIGhhdmUgYmVlbiBidWlsdCBpbiBzdWNoIGEgd2F5IHRoYXQgZXZlcnkgZ3JlYXQgd2FsbCBjb25uZWN0cyBleGFjdGx5IHR3byB0b3ducy4gVGhlIGdyZWF0IHdhbGxzIGRvIG5vdCBjcm9zcyBlYWNoIG90aGVyLiBUaHVzLCB0aGUgY291bnRyeSBpcyBkaXZpZGVkIGludG8gc3VjaCByZWdpb25zIHRoYXQgdG8gbW92ZSBmcm9tIG9uZSByZWdpb24gdG8gYW5vdGhlciwgaXQgaXMgbmVjZXNzYXJ5IHRvIGdvIHRocm91Z2ggYSB0b3duIG9yIGNyb3NzIGEgZ3JlYXQgd2FsbC4gRm9yIGFueSB0d28gdG93bnMgQSBhbmQgQiwgdGhlcmUgaXMgYXQgbW9zdCBvbmUgZ3JlYXQgd2FsbCB3aXRoIG9uZSBlbmQgaW4gQSBhbmQgdGhlIG90aGVyIGluIEIsIGFuZCBmdXJ0aGVyLCBpdCBpcyBwb3NzaWJsZSB0byBnbyBmcm9tIEEgdG8gQiBieSBhbHdheXMgd2Fsa2luZyBpbiBhIHRvd24gb3IgYWxvbmcgYSBncmVhdCB3YWxsLiBUaGUgaW5wdXQgZm9ybWF0IGltcGxpZXMgYWRkaXRpb25hbCByZXN0cmljdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgY2x1YiB3aG9zZSBtZW1iZXJzIGxpdmUgaW4gdGhlIHRvd25zLiBJbiBlYWNoIHRvd24sIHRoZXJlIGlzIG9ubHkgb25lIG1lbWJlciBvciB0aGVyZSBhcmUgbm8gbWVtYmVycyBhdCBhbGwuIFRoZSBtZW1iZXJzIHdhbnQgdG8gbWVldCBpbiBvbmUgb2YgdGhlIHJlZ2lvbnMgKG91dHNpZGUgb2YgYW55IHRvd24pLiBUaGUgbWVtYmVycyB0cmF2ZWwgcmlkaW5nIHRoZWlyIGJpY3ljbGVzLiBUaGV5IGRvIG5vdCB3YW50IHRvIGVudGVyIGFueSB0b3ducywgYmVjYXVzZSBvZiB0aGUgdHJhZmZpYywgYW5kIHRoZXkgd2FudCB0byBjcm9zcyBhcyBmZXcgZ3JlYXQgd2FsbHMgYXMgcG9zc2libGUsIGFzIGl0IGlzIGEgbG90IG9mIHRyb3VibGUuIFRvIGdvIHRvIHRoZSBtZWV0aW5nIHJlZ2lvbiwgZWFjaCBtZW1iZXIgbmVlZHMgdG8gY3Jvc3MgYSBudW1iZXIgKHBvc3NpYmx5IDApIG9mIGdyZWF0IHdhbGxzLiBUaGV5IHdhbnQgdG8gZmluZCBzdWNoIGFuIG9wdGltYWwgcmVnaW9uIHRoYXQgdGhlIHN1bSBvZiB0aGVzZSBudW1iZXJzIChjcm9zc2luZy1zdW0sIGZvciBzaG9ydCkgaXMgbWluaW1pemVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzAwcHg7IHdpZHRoOjc2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSB0b3ducyBhcmUgbGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gMSB0byBOLCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgdG93bnMuIEluIEZpZ3VyZSAxLCB0aGUgbGFiZWxlZCBub2RlcyByZXByZXNlbnQgdGhlIHRvd25zIGFuZCB0aGUgbGluZXMgY29ubmVjdGluZyB0aGUgbm9kZXMgcmVwcmVzZW50IHRoZSBncmVhdCB3YWxscy4gU3VwcG9zZSB0aGF0IHRoZXJlIGFyZSB0aHJlZSBtZW1iZXJzLCB3aG8gbGl2ZSBpbiB0b3ducyAzLCA2LCBhbmQgOS4gVGhlbiwgYW4gb3B0aW1hbCBtZWV0aW5nIHJlZ2lvbiBhbmQgcmVzcGVjdGl2ZSByb3V0ZXMgZm9yIG1lbWJlcnMgYXJlIHNob3duIGluIEZpZ3VyZSAyLiBUaGUgY3Jvc3Npbmctc3VtIGlzIDI6IHRoZSBtZW1iZXIgZnJvbSB0b3duIDkgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgMiBhbmQgNCwgYW5kIHRoZSBtZW1iZXIgZnJvbSB0b3duIDYgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgNCBhbmQgNy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIHRoZSB0b3ducywgdGhlIHJlZ2lvbnMsIGFuZCB0aGUgY2x1YiBtZW1iZXIgaG9tZSB0b3ducywgY29tcHV0ZXMgYW4gb3B0aW1hbCByZWdpb24gYW5kIHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHJlZ2lvbnMgTSwgMiZsZTtNJmxlOzIwMC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRvd25zIE4sIDMmbGU7TiZsZTsyNTAuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIGNsdWIgbWVtYmVycyBMLCAxJmxlO0wmbGU7MzAsIEwmbGU7Ti4gVGhlIGZvdXJ0aCBsaW5lIGNvbnRhaW5zIEwgZGlzdGluY3QgaW50ZWdlcnMgaW4gaW5jcmVhc2luZyBvcmRlcjogdGhlIGxhYmVscyBvZiB0aGUgdG93bnMgd2hlcmUgdGhlIG1lbWJlcnMgbGl2ZS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhhdCB0aGUgZmlsZSBjb250YWlucyAyTSBsaW5lcyBzbyB0aGF0IHRoZXJlIGlzIGEgcGFpciBvZiBsaW5lcyBmb3IgZWFjaCByZWdpb246IHRoZSBmaXJzdCB0d28gb2YgdGhlIDJNIGxpbmVzIGRlc2NyaWJlIHRoZSBmaXJzdCByZWdpb24sIHRoZSBmb2xsb3dpbmcgdHdvIHRoZSBzZWNvbmQgYW5kIHNvIG9uLiBPZiB0aGUgcGFpciwgdGhlIGZpcnN0IGxpbmUgc2hvd3MgdGhlIG51bWJlciBvZiB0b3ducyBJIG9uIHRoZSBib3JkZXIgb2YgdGhhdCByZWdpb24uIFRoZSBzZWNvbmQgbGluZSBvZiB0aGUgcGFpciBjb250YWlucyBJIGludGVnZXJzOiB0aGUgbGFiZWxzIG9mIHRoZXNlIEkgdG93bnMgaW4gc29tZSBvcmRlciBpbiB3aGljaCB0aGV5IGNhbiBiZSBwYXNzZWQgd2hlbiBtYWtpbmcgYSB0cmlwIGNsb2Nrd2lzZSBhbG9uZyB0aGUgYm9yZGVyIG9mIHRoZSByZWdpb24sIHdpdGggdGhlIGZvbGxvd2luZyBleGNlcHRpb24uIFRoZSBsYXN0IHJlZ2lvbiBpcyB0aGUgJmxkcXVvO291dHNpZGUgcmVnaW9uJnJkcXVvOyBzdXJyb3VuZGluZyBhbGwgdG93bnMgYW5kIG90aGVyIHJlZ2lvbnMsIGFuZCBmb3IgaXQgdGhlIG9yZGVyIG9mIHRoZSBsYWJlbHMgY29ycmVzcG9uZHMgdG8gYSB0cmlwIGluIGNvdW50ZXJjbG9ja3dpc2UgZGlyZWN0aW9uLiBUaGUgb3JkZXIgb2YgdGhlIHJlZ2lvbnMgZ2l2ZXMgYW4gaW50ZWdlciBsYWJlbGluZyB0byB0aGUgcmVnaW9uczogdGhlIGZpcnN0IHJlZ2lvbiBoYXMgbGFiZWwgMSwgdGhlIHNlY29uZCBoYXMgbGFiZWwgMiwgYW5kIHNvIG9uLiBOb3RlIHRoYXQgdGhlIGlucHV0IGluY2x1ZGVzIGFsbCByZWdpb25zIGZvcm1lZCBieSB0aGUgdG93bnMgYW5kIGdyZWF0IHdhbGxzLCBpbmNsdWRpbmcgdGhlICZsZHF1bztvdXRzaWRlIHJlZ2lvbiZyZHF1bzsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXI6IHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbGFiZWwgb2YgYW4gb3B0aW1hbCByZWdpb24uIFRoZXJlIG1heSBiZSBzZXZlcmFsIGRpZmZlcmVudCBzb2x1dGlvbnMgZm9yIHRoZSByZWdpb24gYW5kIHlvdXIgcHJvZ3JhbSBuZWVkcyB0byBvdXRwdXQgb25seSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2000 4번

  • 문제의 오타를 찾은 사람: august14