시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 36 15 9 47.368%

문제

어떤 나라에는 커다란 담장이 여러 개 건설되어, 한 담장의 양 끝은 정확히 두 마을과 연결이 돼 있다. 이 문제에서 마을은 점으로, 담장은 마을을 연결하는 선으로 표현된다. 담끼리 교차하는 경우는 없다. 그래서 이 나라는 담장 때문에 국토가 여러 "구역"으로 나눠지게 되는데, 한 구역에서 다른 구역으로 가려면 마을을 통과하거나 담을 넘어야 한다. 각 담장들은 모두 서로 이어져 있기 때문에 임의의 마을 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
W3sicHJvYmxlbV9pZCI6IjIzNjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZjRcdWM3YTUgXHViMTA4XHViYTM4XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHViMDk4XHViNzdjXHVjNWQwXHViMjk0IFx1Y2VlNFx1YjJlNFx1Yjc4MCBcdWIyZjRcdWM3YTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWFjNzRcdWMxMjRcdWI0MThcdWM1YjQsIFx1ZDU1YyBcdWIyZjRcdWM3YTVcdWM3NTggXHVjNTkxIFx1YjA1ZFx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViNDUwIFx1YjljOFx1Yzc0NFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWM3NzQgXHViM2ZjIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWI5YzhcdWM3NDRcdWM3NDAgXHVjODEwXHVjNzNjXHViODVjLCBcdWIyZjRcdWM3YTVcdWM3NDAgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWIyZjRcdWIwN2NcdWI5YWMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWM3NzQgXHViMDk4XHViNzdjXHViMjk0IFx1YjJmNFx1YzdhNSBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhZDZkXHVkMWEwXHVhYzAwIFx1YzVlY1x1YjdlYyAmcXVvdDtcdWFkNmNcdWM1ZWQmcXVvdDtcdWM3M2NcdWI4NWMgXHViMDk4XHViMjIwXHVjOWMwXHVhYzhjIFx1YjQxOFx1YjI5NFx1YjM3MCwgXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1YWMwMFx1YjgyNFx1YmE3NCBcdWI5YzhcdWM3NDRcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHVhYzcwXHViMDk4IFx1YjJmNFx1Yzc0NCBcdWIxMThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViMmY0XHVjN2E1XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjljOFx1Yzc0NCBBXHVjNjQwIEJcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDU1Y1x1Y2FiZCBcdWIwNWRcdWM3NzQgQVx1Yzc3NFx1YWM3MFx1YjA5OCBCXHVjNzc4IFx1YjJmNFx1YzdhNVx1Yzc3NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwLCBcdWFjZTBcdWI5YmRcdWIzZmMgXHVjNzg4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc3NCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWIyZjRcdWM3YTVcdWI5Y2MgXHViNTMwXHViNzdjIFx1YWM3OFx1YzViNFx1YWMwMFx1YmE3NCBBXHVjNWQwXHVjMTFjIEJcdWFlNGNcdWM5YzAgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjRlNCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWIzMDBcdWMwYzFcdWM3M2NcdWI4NWMgXHVkNTU4XHViMjk0IFx1YmFhOFx1Yzc4NFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViOWM4XHVjNzQ0XHViOWM4XHViMmU0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHViYTg1XHVjNzc0IFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWFjMDBcdWM3ODVcdWQ1NzQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJhYThcdWM3ODRcdWM1ZDAgXHVhYzAwXHVjNzg1XHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQ1NWMgXHViYTg1XHViM2M0IFx1YzVjNlx1YjI5NCBcdWI5YzhcdWM3NDRcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAsIFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWI0ZTAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YjljOFx1Yzc0NCBcdWJjMTRcdWFlNjVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWMxMWMgXHViOWNjXHViMDk4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHVhZTMwIFx1ZDY4Y1x1YzZkMFx1YjRlNFx1Yzc0MCBcdWM3OTBcdWM4MDRcdWFjNzBcdWI5N2MgXHVkMGMwXHVhY2UwIFx1YWRmOCBcdWM1N2RcdWMxOGRcdWM3YTVcdWMxOGNcdWI4NWMgXHVhYzAwXHViMjk0XHViMzcwLCBcdWFkNTBcdWQxYjUgXHViYjM4XHVjODFjIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWI5YzhcdWM3NDRcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDBcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjIFx1YjJmNFx1YzdhNVx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YzgwMVx1YWM4YyBcdWIxMThcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM3NzRcdWI0ZTRcdWM3NDAsIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzAxIFx1ZDY4Y1x1YzZkMFx1YjRlNFx1Yzc3NCBcdWIyZjRcdWM3YTVcdWM3NDQgXHViMTE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHViNDE4XHViMjk0IFx1YWNmM1x1Yzc0NCBcdWNjM2VcdWM1NDQgXHVhYzcwXHVhZTMwXHVjMTFjIFx1YmFhOFx1Yzc3NFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTk5XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDNcL3d3LnBuZ1wiIHdpZHRoPVwiNDk1XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIChOXHVjNzQwIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWNkMWQgXHVhYzFjXHVjMjE4KSBcdWFkZjhcdWI5YmMgMVx1Yzc0NCBcdWJjZjRcdWJhNzQsIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWI5YzhcdWM3NDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NDQgXHVjNzg3XHViMjk0IFx1YzEyMFx1Yzc0MCBcdWIyZjRcdWM3YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHVjNzg0XHVjNWQwIFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDAgM1x1YmM4OCwgNlx1YmM4OCwgOVx1YmM4OCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YzUyOSBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMsIFx1Yzc3NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjODA0XHVjY2I0XHVjODAxXHVjNzNjXHViODVjIFx1YjJmNFx1YzdhNVx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVhYzhjIFx1YWM3MFx1Y2NkMFx1YzExYyBcdWJhYThcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MDFcdWQ1NjlcdWQ1NWMgXHVhY2YzXHVjNzQwIFx1YWRmOFx1YjliYyAyXHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5OCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzc0XHViMmU0LiBcdWFjMDEgXHViOWM4XHVjNzQ0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQ2NTRcdWMwYjRcdWQ0NWMgXHVjZTVjIFx1YjMwMFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmY0XHVjN2E1XHVjNzQ0IFx1YjExOFx1Yzc0MCBcdWNkMWRcdWQ2OWZcdWMyMThcdWIyOTQgMlx1Yzc3NFx1YjJlNC4gNlx1YmM4OCBcdWMwYWNcdWI3OGNcdWM3NzQgNFx1YmM4OFx1YWNmYyA3XHViYzg4IFx1YjljOFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjJmNFx1Yzc0NCBcdWIxMThcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCA5XHViYzg4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCAyXHViYzg4XHVhY2ZjIDRcdWJjODggXHViOWM4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmY0XHVjNzQ0IFx1YjExOFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1YWNmYyBcdWIyZjRcdWM3YTUsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJhYThcdWM3ODRcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzkwXHViOGNjXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NCwgXHViYWE4XHVjNzc0XHVhZTMwXHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWQ1NjlcdWQ1NWMgXHVhZDZjXHVjNWVkXHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YWNlMCZuYnNwO1x1YjJmNFx1YzdhNVx1Yzc0NCBcdWIxMThcdWIyOTQgXHVjZDFkXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0XHVjNzg4XHViMmU0KDImbHQ7PU0mbHQ7PSAyMDApLiAoXHVhZGY4XHViOWJjIDFcdWM3NDQgXHVjMGI0XHVkM2I0XHViY2Y0XHViYTc0IFx1YzBkZFx1YWNhOFx1YjA5YyBcdWIyZTRcdWFjMDFcdWQ2MTUgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWNiZFx1YWNjNCBcdWJjMTRcdWFlNjVcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjIDEwXHVhYzFjXHVjNzg0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjggXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc3Y1x1Y2VlYlx1YjI5NFx1YjJlNC4pIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0KFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFmMmRcdWM5ZDNcdWM4MTApXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0XHVjNzg4XHViMmU0KDImbHQ7PU4mbHQ7PSAyNTApLiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOFx1Yzc4NFx1YzVkMCBcdWI0ZTAgXHVkNjhjXHVjNmQwXHVjNzU4IFx1YzIxOCBMXHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNCgxJmx0Oz1MJmx0Oz0zMCwgTCZsdDs9TikuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIxMzdcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ2OGNcdWM2ZDBcdWM3NzQgXHVjMGFjXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IExcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgMk1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVhYzcwXHVhZTMwXHVjMTFjIFx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzQgXHVhZDZjXHVjNWVkXHVjNzc0IFx1YWMxMFx1YzJmOFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHVhYzFjXHVjMjE4IElcdWFjMDAgXHViNGU0XHVjNWI0XHVjNzg4XHVjNzNjXHViYTcwLCBcdWIyZTRcdWM3NGNcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjljOFx1Yzc0NCBJXHVhYzFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YjljYywgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWM2MDhcdWM2NzhcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NDAoTVx1YzlmOCBcdWFkNmNcdWM1ZWQpIFx1YjljOFx1Yzc0NCBcdWM4MDRcdWNjYjRcdWM3NTggXHViYzE0XHVhZTY1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIyZTRcdWI4ZjAgXHViNTRjXHViOWNjXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWJjMTRcdWFlNjVcdWM3NDQgXHVhYzEwXHVjMmY4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTUgXHVjMjFjXHVjMTFjXHViODVjIFx1YzgxY1x1YzJkY1x1YjQxY1x1YjJlNC4gXHVjNzc0XHViODA3XHViNGVmIFx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM1ZDBcdWIyOTQgXHViMmY0XHVhY2ZjIFx1YjljOFx1Yzc0NFx1Yjg1YyBcdWM3NzhcdWQ1NzQgXHVjMGRkXHVhY2E4XHViMDljIFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWJjMTRcdWFlNjVcdWNhYmQgXHVhZDZjXHVjNWVkXHVhZTRjXHVjOWMwIFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyBcdWJhYThcdWI0NTAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkNmNcdWM1ZWRcdWM3NDAgXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1YzVkMCBcdWMyMThcdWI4NWRcdWIzZmMgXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWFjZTcgXHVhZGY4IFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWM5YzBcdWM4MTVcdWQ1NThcdWIyOTQgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCBcdWIwOThcdWM2MjRcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzc0IDFcdWJjODggXHVhZDZjXHVjNWVkLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWRcdWM3NzQgMlx1YmM4OFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWJhYThcdWM3NzRcdWFlMzBcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1ZDU2OVx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM3NDQgXHVhYzAwXHViOWFjXHVkMGFjIFx1YjU0Y1x1YjI5NCBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjXHVjNWQwXHVjMTFjIFx1YmE4N1x1YzlmOFx1Yjg1YyBcdWIwOThcdWM2MjggXHVhZDZjXHVjNWVkXHVjNzc4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjVcdWM1NDggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWQ2Y1x1ZDU1YyBcdWNkMWRcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWIxMThcdWFjZTAgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWFkNmNcdWM1ZWRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1NWMgXHVhY2YzXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldhbGxzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGNvdW50cnksIGdyZWF0IHdhbGxzIGhhdmUgYmVlbiBidWlsdCBpbiBzdWNoIGEgd2F5IHRoYXQgZXZlcnkgZ3JlYXQgd2FsbCBjb25uZWN0cyBleGFjdGx5IHR3byB0b3ducy4gVGhlIGdyZWF0IHdhbGxzIGRvIG5vdCBjcm9zcyBlYWNoIG90aGVyLiBUaHVzLCB0aGUgY291bnRyeSBpcyBkaXZpZGVkIGludG8gc3VjaCByZWdpb25zIHRoYXQgdG8gbW92ZSBmcm9tIG9uZSByZWdpb24gdG8gYW5vdGhlciwgaXQgaXMgbmVjZXNzYXJ5IHRvIGdvIHRocm91Z2ggYSB0b3duIG9yIGNyb3NzIGEgZ3JlYXQgd2FsbC4gRm9yIGFueSB0d28gdG93bnMgQSBhbmQgQiwgdGhlcmUgaXMgYXQgbW9zdCBvbmUgZ3JlYXQgd2FsbCB3aXRoIG9uZSBlbmQgaW4gQSBhbmQgdGhlIG90aGVyIGluIEIsIGFuZCBmdXJ0aGVyLCBpdCBpcyBwb3NzaWJsZSB0byBnbyBmcm9tIEEgdG8gQiBieSBhbHdheXMgd2Fsa2luZyBpbiBhIHRvd24gb3IgYWxvbmcgYSBncmVhdCB3YWxsLiBUaGUgaW5wdXQgZm9ybWF0IGltcGxpZXMgYWRkaXRpb25hbCByZXN0cmljdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgY2x1YiB3aG9zZSBtZW1iZXJzIGxpdmUgaW4gdGhlIHRvd25zLiBJbiBlYWNoIHRvd24sIHRoZXJlIGlzIG9ubHkgb25lIG1lbWJlciBvciB0aGVyZSBhcmUgbm8gbWVtYmVycyBhdCBhbGwuIFRoZSBtZW1iZXJzIHdhbnQgdG8gbWVldCBpbiBvbmUgb2YgdGhlIHJlZ2lvbnMgKG91dHNpZGUgb2YgYW55IHRvd24pLiBUaGUgbWVtYmVycyB0cmF2ZWwgcmlkaW5nIHRoZWlyIGJpY3ljbGVzLiBUaGV5IGRvIG5vdCB3YW50IHRvIGVudGVyIGFueSB0b3ducywgYmVjYXVzZSBvZiB0aGUgdHJhZmZpYywgYW5kIHRoZXkgd2FudCB0byBjcm9zcyBhcyBmZXcgZ3JlYXQgd2FsbHMgYXMgcG9zc2libGUsIGFzIGl0IGlzIGEgbG90IG9mIHRyb3VibGUuIFRvIGdvIHRvIHRoZSBtZWV0aW5nIHJlZ2lvbiwgZWFjaCBtZW1iZXIgbmVlZHMgdG8gY3Jvc3MgYSBudW1iZXIgKHBvc3NpYmx5IDApIG9mIGdyZWF0IHdhbGxzLiBUaGV5IHdhbnQgdG8gZmluZCBzdWNoIGFuIG9wdGltYWwgcmVnaW9uIHRoYXQgdGhlIHN1bSBvZiB0aGVzZSBudW1iZXJzIChjcm9zc2luZy1zdW0sIGZvciBzaG9ydCkgaXMgbWluaW1pemVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzAwcHg7IHdpZHRoOjc2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSB0b3ducyBhcmUgbGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gMSB0byBOLCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgdG93bnMuIEluIEZpZ3VyZSAxLCB0aGUgbGFiZWxlZCBub2RlcyByZXByZXNlbnQgdGhlIHRvd25zIGFuZCB0aGUgbGluZXMgY29ubmVjdGluZyB0aGUgbm9kZXMgcmVwcmVzZW50IHRoZSBncmVhdCB3YWxscy4gU3VwcG9zZSB0aGF0IHRoZXJlIGFyZSB0aHJlZSBtZW1iZXJzLCB3aG8gbGl2ZSBpbiB0b3ducyAzLCA2LCBhbmQgOS4gVGhlbiwgYW4gb3B0aW1hbCBtZWV0aW5nIHJlZ2lvbiBhbmQgcmVzcGVjdGl2ZSByb3V0ZXMgZm9yIG1lbWJlcnMgYXJlIHNob3duIGluIEZpZ3VyZSAyLiBUaGUgY3Jvc3Npbmctc3VtIGlzIDI6IHRoZSBtZW1iZXIgZnJvbSB0b3duIDkgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgMiBhbmQgNCwgYW5kIHRoZSBtZW1iZXIgZnJvbSB0b3duIDYgaGFzIHRvIGNyb3NzIHRoZSBncmVhdCB3YWxsIGJldHdlZW4gdG93bnMgNCBhbmQgNy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIHRoZSB0b3ducywgdGhlIHJlZ2lvbnMsIGFuZCB0aGUgY2x1YiBtZW1iZXIgaG9tZSB0b3ducywgY29tcHV0ZXMgYW4gb3B0aW1hbCByZWdpb24gYW5kIHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHJlZ2lvbnMgTSwgMiZsZTtNJmxlOzIwMC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRvd25zIE4sIDMmbGU7TiZsZTsyNTAuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIGNsdWIgbWVtYmVycyBMLCAxJmxlO0wmbGU7MzAsIEwmbGU7Ti4gVGhlIGZvdXJ0aCBsaW5lIGNvbnRhaW5zIEwgZGlzdGluY3QgaW50ZWdlcnMgaW4gaW5jcmVhc2luZyBvcmRlcjogdGhlIGxhYmVscyBvZiB0aGUgdG93bnMgd2hlcmUgdGhlIG1lbWJlcnMgbGl2ZS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhhdCB0aGUgZmlsZSBjb250YWlucyAyTSBsaW5lcyBzbyB0aGF0IHRoZXJlIGlzIGEgcGFpciBvZiBsaW5lcyBmb3IgZWFjaCByZWdpb246IHRoZSBmaXJzdCB0d28gb2YgdGhlIDJNIGxpbmVzIGRlc2NyaWJlIHRoZSBmaXJzdCByZWdpb24sIHRoZSBmb2xsb3dpbmcgdHdvIHRoZSBzZWNvbmQgYW5kIHNvIG9uLiBPZiB0aGUgcGFpciwgdGhlIGZpcnN0IGxpbmUgc2hvd3MgdGhlIG51bWJlciBvZiB0b3ducyBJIG9uIHRoZSBib3JkZXIgb2YgdGhhdCByZWdpb24uIFRoZSBzZWNvbmQgbGluZSBvZiB0aGUgcGFpciBjb250YWlucyBJIGludGVnZXJzOiB0aGUgbGFiZWxzIG9mIHRoZXNlIEkgdG93bnMgaW4gc29tZSBvcmRlciBpbiB3aGljaCB0aGV5IGNhbiBiZSBwYXNzZWQgd2hlbiBtYWtpbmcgYSB0cmlwIGNsb2Nrd2lzZSBhbG9uZyB0aGUgYm9yZGVyIG9mIHRoZSByZWdpb24sIHdpdGggdGhlIGZvbGxvd2luZyBleGNlcHRpb24uIFRoZSBsYXN0IHJlZ2lvbiBpcyB0aGUgJmxkcXVvO291dHNpZGUgcmVnaW9uJnJkcXVvOyBzdXJyb3VuZGluZyBhbGwgdG93bnMgYW5kIG90aGVyIHJlZ2lvbnMsIGFuZCBmb3IgaXQgdGhlIG9yZGVyIG9mIHRoZSBsYWJlbHMgY29ycmVzcG9uZHMgdG8gYSB0cmlwIGluIGNvdW50ZXJjbG9ja3dpc2UgZGlyZWN0aW9uLiBUaGUgb3JkZXIgb2YgdGhlIHJlZ2lvbnMgZ2l2ZXMgYW4gaW50ZWdlciBsYWJlbGluZyB0byB0aGUgcmVnaW9uczogdGhlIGZpcnN0IHJlZ2lvbiBoYXMgbGFiZWwgMSwgdGhlIHNlY29uZCBoYXMgbGFiZWwgMiwgYW5kIHNvIG9uLiBOb3RlIHRoYXQgdGhlIGlucHV0IGluY2x1ZGVzIGFsbCByZWdpb25zIGZvcm1lZCBieSB0aGUgdG93bnMgYW5kIGdyZWF0IHdhbGxzLCBpbmNsdWRpbmcgdGhlICZsZHF1bztvdXRzaWRlIHJlZ2lvbiZyZHF1bzsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXI6IHRoZSBtaW5pbWFsIGNyb3NzaW5nLXN1bS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbGFiZWwgb2YgYW4gb3B0aW1hbCByZWdpb24uIFRoZXJlIG1heSBiZSBzZXZlcmFsIGRpZmZlcmVudCBzb2x1dGlvbnMgZm9yIHRoZSByZWdpb24gYW5kIHlvdXIgcHJvZ3JhbSBuZWVkcyB0byBvdXRwdXQgb25seSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2000 4번

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