시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 24 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+XHJcbjxwPlxyXG5cdCZuYnNwOyBcdWI5YzhcdWM3NDRcdWFjZmMgXHViMmY0XHVjN2E1LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHVjNzg0XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Yzc5MFx1YjhjY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDQsIFx1YmFhOFx1Yzc3NFx1YWUzMFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVkNTY5XHVkNTVjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWFjZTAmbmJzcDtcdWIyZjRcdWM3YTVcdWM3NDQgXHViMTE4XHViMjk0IFx1Y2QxZFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHQmbmJzcDsgXHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwXHViMjk0IFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NFx1Yzc4OFx1YjJlNCgyJmx0Oz1NJmx0Oz0gMjAwKS4gKFx1YWRmOFx1YjliYyAxXHVjNzQ0IFx1YzBiNFx1ZDNiNFx1YmNmNFx1YmE3NCBcdWMwZGRcdWFjYThcdWIwOWMgXHViMmU0XHVhYzAxXHVkNjE1IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjYmRcdWFjYzQgXHViYzE0XHVhZTY1XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyAxMFx1YWMxY1x1Yzc4NFx1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM3N2NcdWNlZWJcdWIyOTRcdWIyZTQuKSBcdWI0NThcdWM5ZjhcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0KFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFmMmRcdWM5YzBcdWM4MTApXHVjNzU4XHVhYzFjXHVjMjE4Tlx1Yzc3NFx1Yzc4OFx1YjJlNCgyJmx0Oz1OJmx0Oz0gMjUwKS4gXHVjMTRiXHVjOWY4XHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWI0ZTAgXHVkNjhjXHVjNmQwXHVjNzU4XHVjMjE4TFx1Yzc3NFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNCgxJmx0Oz1MJmx0Oz0zMCwgTCZsdDs9TikuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIxMzdcdWM5ZjhcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDY4Y1x1YzZkMFx1Yzc3NCBcdWMwYWNcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG48cD5cclxuXHQmbmJzcDsgXHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCAyTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVhZDZjXHVjNWVkXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHViNDUwIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LiBcdWFjNzBcdWFlMzBcdWMxMWMgXHVjY2FiXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NCBcdWFkNmNcdWM1ZWRcdWM3NzQgXHVhYzEwXHVjMmY4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWFjMWNcdWMyMTggSVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjJlNFx1Yzc0Y1x1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzQgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHViOWM4XHVjNzQ0IElcdWFjMWNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTUgXHVjMjFjXHVjMTFjXHViODVjIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHViMmU0XHViOWNjLCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzYwOFx1YzY3OFx1YWMwMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMFx1YzdhNSBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1Yzc0MChNXHVjOWY4IFx1YWQ2Y1x1YzVlZCkgXHViOWM4XHVjNzQ0IFx1YzgwNFx1Y2NiNFx1Yzc1OCBcdWJjMTRcdWFlNjVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhZDZjXHVjNWVkXHVjNzQ0IFx1YjJlNFx1YjhmMCBcdWI1NGNcdWI5Y2NcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YmMxNFx1YWU2NVx1Yzc0NCBcdWFjMTBcdWMyZjhcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjljOFx1Yzc0NFx1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViYzE4XHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNSBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjODFjXHVjMmRjXHViNDFjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWI0ZWYgXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1YzVkMFx1YjI5NCBcdWIyZjRcdWFjZmMgXHViOWM4XHVjNzQ0XHViODVjIFx1Yzc3OFx1ZDU3NCBcdWMwZGRcdWFjYThcdWIwOWMgXHViYWE4XHViNGUwIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YmMxNFx1YWU2NVx1Y2FiZCBcdWFkNmNcdWM1ZWRcdWFlNGNcdWM5YzAgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjIFx1YmFhOFx1YjQ1MCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0Jm5ic3A7IFx1YWQ2Y1x1YzVlZFx1Yzc0MCBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjXHVjNWQwIFx1YzIxOFx1Yjg1ZFx1YjNmYyBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVhYzAwIFx1YWNlNyBcdWFkZjggXHVhZDZjXHVjNWVkXHVjNzQ0IFx1YzljMFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHViYTNjXHVjODAwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NzQgMVx1YmM4OCBcdWFkNmNcdWM1ZWQsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1Yzc3NCAyXHViYzg4XHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YmFhOFx1Yzc3NFx1YWUzMFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVkNTY5XHVkNTVjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYWMgXHViNTRjXHViMjk0IFx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM1ZDBcdWMxMWMgXHViYTg3XHVjOWY4XHViODVjIFx1YjA5OFx1YzYyOCBcdWFkNmNcdWM1ZWRcdWM3NzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHQmbmJzcDsmbmJzcDtcdWNjYWJcdWM5ZjhcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmY1XHVjNTQ4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWFkNmNcdWQ1NWMgXHVjZDFkXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWIxMThcdWFjZTAgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWFkNmNcdWM1ZWRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1NWMgXHVhY2YzXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldhbGxzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGNvdW50cnksIGdyZWF0IHdhbGxzIGhhdmUgYmVlbiBidWlsdCBpbiBzdWNoIGEgd2F5IHRoYXQgZXZlcnkgZ3JlYXQgd2FsbCBjb25uZWN0cyBleGFjdGx5IHR3byB0b3ducy4gVGhlIGdyZWF0IHdhbGxzIGRvIG5vdCBjcm9zcyBlYWNoIG90aGVyLiBUaHVzLCB0aGUgY291bnRyeSBpcyBkaXZpZGVkIGludG8gc3VjaCByZWdpb25zIHRoYXQgdG8gbW92ZSBmcm9tIG9uZSByZWdpb24gdG8gYW5vdGhlciwgaXQgaXMgbmVjZXNzYXJ5IHRvIGdvIHRocm91Z2ggYSB0b3duIG9yIGNyb3NzIGEgZ3JlYXQgd2FsbC4gRm9yIGFueSB0d28gdG93bnMgQSBhbmQgQiwgdGhlcmUgaXMgYXQgbW9zdCBvbmUgZ3JlYXQgd2FsbCB3aXRoIG9uZSBlbmQgaW4gQSBhbmQgdGhlIG90aGVyIGluIEIsIGFuZCBmdXJ0aGVyLCBpdCBpcyBwb3NzaWJsZSB0byBnbyBmcm9tIEEgdG8gQiBieSBhbHdheXMgd2Fsa2luZyBpbiBhIHRvd24gb3IgYWxvbmcgYSBncmVhdCB3YWxsLiBUaGUgaW5wdXQgZm9ybWF0IGltcGxpZXMgYWRkaXRpb25hbCByZXN0cmljdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgY2x1YiB3aG9zZSBtZW1iZXJzIGxpdmUgaW4gdGhlIHRvd25zLiBJbiBlYWNoIHRvd24sIHRoZXJlIGlzIG9ubHkgb25lIG1lbWJlciBvciB0aGVyZSBhcmUgbm8gbWVtYmVycyBhdCBhbGwuIFRoZSBtZW1iZXJzIHdhbnQgdG8gbWVldCBpbiBvbmUgb2YgdGhlIHJlZ2lvbnMgKG91dHNpZGUgb2YgYW55IHRvd24pLiBUaGUgbWVtYmVycyB0cmF2ZWwgcmlkaW5nIHRoZWlyIGJpY3ljbGVzLiBUaGV5IGRvIG5vdCB3YW50IHRvIGVudGVyIGFueSB0b3ducywgYmVjYXVzZSBvZiB0aGUgdHJhZmZpYywgYW5kIHRoZXkgd2FudCB0byBjcm9zcyBhcyBmZXcgZ3JlYXQgd2FsbHMgYXMgcG9zc2libGUsIGFzIGl0IGlzIGEgbG90IG9mIHRyb3VibGUuIFRvIGdvIHRvIHRoZSBtZWV0aW5nIHJlZ2lvbiwgZWFjaCBtZW1iZXIgbmVlZHMgdG8gY3Jvc3MgYSBudW1iZXIgKHBvc3NpYmx5IDApIG9mIGdyZWF0IHdhbGxzLiBUaGV5IHdhbnQgdG8gZmluZCBzdWNoIGFuIG9wdGltYWwgcmVnaW9uIHRoYXQgdGhlIHN1bSBvZiB0aGVzZSBudW1iZXJzIChjcm9zc2luZy1zdW0sIGZvciBzaG9ydCkgaXMgbWluaW1pemVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzAwcHg7IHdpZHRoOjc2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSB0b3ducyBhcmUgbGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gMSB0byBOLCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgdG93bnMuIEluIEZpZ3VyZSAxLCB0aGUgbGFiZWxlZCBub2RlcyByZXByZXNlbnQgdGhlIHRvd25zIGFuZCB0aGUgbGluZXMgY29ubmVjdGluZyB0aGUgbm9kZXMgcmVwcmVzZW50IHRoZSBncmVhdCB3YWxscy4gU3VwcG9zZSB0aGF0IHRoZXJlIGFyZSB0aHJlZSBtZW1iZXJzLCB3aG8gbGl2ZSBpbiB0b3ducyAzLCA2LCBhbmQgOS4gVGhlbiwgYW4gb3B0aW1hbCBtZWV0aW5nIHJlZ2lvbiBhbmQgcmVzcGVjdGl2ZSByb3V0ZXMgZm9yIG1lbWJlcnMgYXJlIHNob3duIGluIEZpZ3VyZSAyLiBUaGUgY3Jvc3Npbmctc3VtIGlzIDI6IHRoZSBtZW1iZXIgZnJvbSB0b3duIDkgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgMiBhbmQgNCwgYW5kIHRoZSBtZW1iZXIgZnJvbSB0b3duIDYgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgNCBhbmQgNy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIHRoZSB0b3ducywgdGhlIHJlZ2lvbnMsIGFuZCB0aGUgY2x1YiBtZW1iZXIgaG9tZSB0b3ducywgY29tcHV0ZXMgYW4gb3B0aW1hbCByZWdpb24gYW5kIHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHJlZ2lvbnMgTSwgMiZsZTtNJmxlOzIwMC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRvd25zIE4sIDMmbGU7TiZsZTsyNTAuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIGNsdWIgbWVtYmVycyBMLCAxJmxlO0wmbGU7MzAsIEwmbGU7Ti4gVGhlIGZvdXJ0aCBsaW5lIGNvbnRhaW5zIEwgZGlzdGluY3QgaW50ZWdlcnMgaW4gaW5jcmVhc2luZyBvcmRlcjogdGhlIGxhYmVscyBvZiB0aGUgdG93bnMgd2hlcmUgdGhlIG1lbWJlcnMgbGl2ZS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhhdCB0aGUgZmlsZSBjb250YWlucyAyTSBsaW5lcyBzbyB0aGF0IHRoZXJlIGlzIGEgcGFpciBvZiBsaW5lcyBmb3IgZWFjaCByZWdpb246IHRoZSBmaXJzdCB0d28gb2YgdGhlIDJNIGxpbmVzIGRlc2NyaWJlIHRoZSBmaXJzdCByZWdpb24sIHRoZSBmb2xsb3dpbmcgdHdvIHRoZSBzZWNvbmQgYW5kIHNvIG9uLiBPZiB0aGUgcGFpciwgdGhlIGZpcnN0IGxpbmUgc2hvd3MgdGhlIG51bWJlciBvZiB0b3ducyBJIG9uIHRoZSBib3JkZXIgb2YgdGhhdCByZWdpb24uIFRoZSBzZWNvbmQgbGluZSBvZiB0aGUgcGFpciBjb250YWlucyBJIGludGVnZXJzOiB0aGUgbGFiZWxzIG9mIHRoZXNlIEkgdG93bnMgaW4gc29tZSBvcmRlciBpbiB3aGljaCB0aGV5IGNhbiBiZSBwYXNzZWQgd2hlbiBtYWtpbmcgYSB0cmlwIGNsb2Nrd2lzZSBhbG9uZyB0aGUgYm9yZGVyIG9mIHRoZSByZWdpb24sIHdpdGggdGhlIGZvbGxvd2luZyBleGNlcHRpb24uIFRoZSBsYXN0IHJlZ2lvbiBpcyB0aGUgJmxkcXVvO291dHNpZGUgcmVnaW9uJnJkcXVvOyBzdXJyb3VuZGluZyBhbGwgdG93bnMgYW5kIG90aGVyIHJlZ2lvbnMsIGFuZCBmb3IgaXQgdGhlIG9yZGVyIG9mIHRoZSBsYWJlbHMgY29ycmVzcG9uZHMgdG8gYSB0cmlwIGluIGNvdW50ZXJjbG9ja3dpc2UgZGlyZWN0aW9uLiBUaGUgb3JkZXIgb2YgdGhlIHJlZ2lvbnMgZ2l2ZXMgYW4gaW50ZWdlciBsYWJlbGluZyB0byB0aGUgcmVnaW9uczogdGhlIGZpcnN0IHJlZ2lvbiBoYXMgbGFiZWwgMSwgdGhlIHNlY29uZCBoYXMgbGFiZWwgMiwgYW5kIHNvIG9uLiBOb3RlIHRoYXQgdGhlIGlucHV0IGluY2x1ZGVzIGFsbCByZWdpb25zIGZvcm1lZCBieSB0aGUgdG93bnMgYW5kIGdyZWF0IHdhbGxzLCBpbmNsdWRpbmcgdGhlICZsZHF1bztvdXRzaWRlIHJlZ2lvbiZyZHF1bzsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXI6IHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbGFiZWwgb2YgYW4gb3B0aW1hbCByZWdpb24uIFRoZXJlIG1heSBiZSBzZXZlcmFsIGRpZmZlcmVudCBzb2x1dGlvbnMgZm9yIHRoZSByZWdpb24gYW5kIHlvdXIgcHJvZ3JhbSBuZWVkcyB0byBvdXRwdXQgb25seSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2000 4번

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