시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB476292262620.860%

문제

과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다.

얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다.

일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에서 스페인어를 과외 받았다.

오랜 고서에 의하면, 고대 마야인은 하늘을 날아다니는 재주가 있었다고 한다. 과외맨은 매일 밤 하늘을 바라보며 마야인들의 흔적을 찾으려고 애를 썼다.

그렇게 한 달이 지났을까... 한국에선 이민혁 실종 사건이 연일 대서특필 되고 있고, 사람들은 사라진 과외맨을 찾으며 시청 광장에서 촛불 집회를 했다. 과외맨도 이런 사실에 안타까움을 느꼈다. 하지만, 과외 노트 없는 과외맨은 평범한 대학생과 같기 때문에 아직 돌아갈 수 없었다.

과외 노트의 단서는 뜻하지 않게 스페인어 과외를 받던 중에 알게 되었다. 과외맨의 과외 선생님이 주말을 이용해서 등산을 하던 사이에 고대 마야의 사원으로 보이는 것을 발견했고, 민혁이에게 과외 노트가 거기에 있는 것 같다고 알려주었다.

과외맨은 즉시 과외 노트를 찾으러 고대 마야의 사원으로 여행을 떠났다.

고대 마야의 사원의 입구로 들어간 과외맨은 매우 놀랐다. 바로 과외 노트가 자신의 눈 앞에 있는 것 이었다. 과외맨은 이적의 다행이다를 부르면서 과외 노트를 집으려고 했지만, 그것은 노트의 홀로그램이었다. 이어서 고대 마야인의 목소리가 사원을 가득 채우기 시작했다. 하지만, 고대 마야인은 스페인어를 사용하지 않았다. 과외맨은 닥터후에게 전화를 걸어서 자신에게 타디스의 번역 프로토콜을 제공해 줄 수 있는지를 물어 보았다. 닥터는 흔쾌히 요청을 받아들였고, 민혁이는 마야인의 메시지를 듣기 위해 밖으로 나갔다가 다시 들어왔다.

"하하하. 과외 노트를 돌려 받고 싶나? 그럼 여기로 와서 가져가 보시지. 하하하하"

과외맨의 과외 노트는 입구의 반대편에 있고, 그 사이에는 절벽이 있었다. 갑자기 하늘에서 거대한 도미노 타일이 떨어졌고, 그 사이를 연결하는 다리를 만들었다.

도미노 타일은 두 조각으로 나누어져 있었고, 각 조각은 정사각형이다. 조각에는 1과 6사이의 숫자가 써져 있다.

타일은 N줄로 놓여져 있고, 홀수 줄에는 N개의 타일이, 짝수 줄에는 N-1개의 타일이 놓여져 있다. 아래 그림은 (N=5)일 때 타일이 놓여져 있는 형태이다.

한 타일에서 다른 타일로 넘어가려면, 두 타일이 인접해야 한다. 또, 같은 변을 공유하는 조각에 쓰여 있는 숫자가 같아야 한다.

과외맨은 반대편으로 넘어가기 위해서 첫 줄의 가장 첫 타일에서 마지막 줄의 가장 마지막 타일로 이동하는 가장 짧은 경로를 찾으려고 한다.

타일은 row-major order에 의해서 번호가 매겨져 있으며, 첫 번째 줄의 첫 타일의 번호는 1, 마지막 타일의 번호는 N이다. 두 번째 줄에서 첫 타일의 번호는 N+1이고, 마지막 타일의 번호는 2*N-1이다.

첫 줄의 첫 타일로만 과외맨이 들어갈 수 있고, 마지막 줄의 마지막 타일위에 과외 노트가 놓여져 있다.

마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른쪽에 쓰여 있는 숫자는 Bi이다.

출력

첫째 줄에 가장 짧은 경로의 길이 (타일의 개수)를 출력한다.

둘째 줄에는 경로 상의 타일의 번호를 공백으로 구분하여 순서대로 출력한다. 만약, 가장 짧은 경로가 여러 가지라면, 아무거나 출력하면 된다.

예제 입력 1

5
1 4
4 5
3 4
5 4
5 2
4 2
5 6
4 4
6 5
2 4
5 1
6 1
1 6
2 3
4 2
5 3
1 2
5 5
4 1
2 2
4 3
2 3
3 4

예제 출력 1

7
1 2 7 12 17 22 23

예제 입력 2

3
1 2
2 3
6 6
2 4
3 5
6 6
4 5
5 6

예제 출력 2

4
1 2 5 8

예제 입력 3

4
1 5
5 3
5 5
5 6
5 3
6 4
4 5
2 5
2 4
4 3
2 4
5 2
1 4
1 6

예제 출력 3

7
1 5 8 12 9 10 13
W3sicHJvYmxlbV9pZCI6IjUyMTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWM2NzhcdWI5ZTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBcdWQzYzlcdWMxOGNcdWM1ZDAgXHVjMTFjXHVhYzE1XHViMzAwXHVkNTU5XHVhZDUwIFx1ZDU1OVx1YzBkZCBcdWM3NzRcdWJiZmNcdWQ2MDFcdWM3M2NcdWI4NWMgXHVjNzA0XHVjN2E1XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQ1NWNcdWFkNmRcdWM3NTggXHViMzAwXHVkNDVjXHVjODAxXHVjNzc4IFx1YzYwMVx1YzZjNVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViMjk0IFx1YzI4OFx1ZDM3YyBcdWQ3ODhcdWM1YjRcdWI4NWNcdWFjMDAgXHViMTA4XHViYjM0IFx1YmJmOFx1YWQ2ZFx1YzVkMCBcdWM5ZDFcdWM5MTFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1ZDYwNFx1YzJlNFx1Yzc0NCBcdWM1NDhcdWQwYzBcdWFlNGNcdWM2Y2NcdWQ1ODhcdWFjZTAsIFx1YWRmOFx1Yzc1OCBcdWM4MDhcdWNlNWNcdWQ1NWMgXHVjZTVjXHVhZDZjXHVjNzc4IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1YjM1NFx1YjllOFx1YWNmYyBcdWM1NDRcdWM3NzRcdWM1YjhcdWI5ZThcdWM1ZDBcdWFjOGMgXHVkNTVjXHVhZDZkXHVjNzNjXHViODVjIFx1YzY0MFx1YzExYyBcdWFjMTlcdWM3NzQgXHVjNjAxXHVjNmM1IFx1ZDY1Y1x1YjNkOVx1Yzc0NCBcdWQ1NThcdWM3OTBcdWIyOTQgXHVjODFjXHVjNTQ4XHVjNzQ0IFx1ZDU4OFx1YzczY1x1YjA5OCBcdWFjNzBcdWM4MDhcdWIyZjlcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViY1x1YjljOCBcdWM4MDQsIFx1YzYyNFx1Yjc5YyBcdWM3YTBcdWM1ZDBcdWMxMWMgXHVhZTY4XHVjNWI0XHViMDljIFx1YWNlMFx1YjMwMCBcdWI5YzhcdWM1N2NcdWM3NzhcdWI0ZTRcdWM3NzQgXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzc0IFx1YzIxOFx1YzVjNVx1Yzc0NCBcdWI0ZTNcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YWNmY1x1YzY3OCBcdWIxNzhcdWQyYjhcdWI5N2MgXHVkNmQ0XHVjY2QwXHVhYzE0XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHViZTdjXHVjNTU3XHVhZTM0IFx1YjE3OFx1ZDJiOFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM2MjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Yzc3OFx1Y2M5YyBcdWFjZjVcdWQ1NmRcdWM3M2NcdWI4NWMgXHVhYzAwXHVjMTFjIFx1YWNmY1x1ZDE0Y1x1YjlkMFx1Yjc3Y1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBkNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzdjXHViMmU4IFx1YzViOFx1YzViNFx1YWMwMCBcdWQxYjVcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWQyYjlcdWFlMzBcdWI5N2MgXHVjMGI0XHViODI0XHVjMTFjIFx1Yzc3Y1x1YzhmY1x1Yzc3Y1x1YWMwNCBcdWFjZmNcdWQxNGNcdWI5ZDBcdWI3N2NcdWM1ZDBcdWMxMWMgXHVjMmE0XHVkMzk4XHVjNzc4XHVjNWI0XHViOTdjIFx1YWNmY1x1YzY3OCBcdWJjMWJcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1Yjc5YyBcdWFjZTBcdWMxMWNcdWM1ZDAgXHVjNzU4XHVkNTU4XHViYTc0LCBcdWFjZTBcdWIzMDAgXHViOWM4XHVjNTdjXHVjNzc4XHVjNzQwIFx1ZDU1OFx1YjI5OFx1Yzc0NCBcdWIwYTBcdWM1NDRcdWIyZTRcdWIyYzhcdWIyOTQgXHVjN2FjXHVjOGZjXHVhYzAwIFx1Yzc4OFx1YzVjOFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBcdWI5ZTRcdWM3N2MgXHViYzI0IFx1ZDU1OFx1YjI5OFx1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWJhNzAgXHViOWM4XHVjNTdjXHVjNzc4XHViNGU0XHVjNzU4IFx1ZDc1NFx1YzgwMVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVjNTYwXHViOTdjIFx1YzM3Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViODA3XHVhYzhjIFx1ZDU1YyBcdWIyZWNcdWM3NzQgXHVjOWMwXHViMGFjXHVjNzQ0XHVhZTRjLi4uIFx1ZDU1Y1x1YWQ2ZFx1YzVkMFx1YzEyMCBcdWM3NzRcdWJiZmNcdWQ2MDEgXHVjMmU0XHVjODg1IFx1YzBhY1x1YWM3NFx1Yzc3NCBcdWM1ZjBcdWM3N2MgXHViMzAwXHVjMTFjXHVkMmI5XHVkNTQ0IFx1YjQxOFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMwYWNcdWI3N2NcdWM5YzQgXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzQ0IFx1Y2MzZVx1YzczY1x1YmE3MCBcdWMyZGNcdWNjYWQgXHVhZDExXHVjN2E1XHVjNWQwXHVjMTFjIFx1Y2QxYlx1YmQ4OCBcdWM5ZDFcdWQ2OGNcdWI5N2MgXHVkNTg4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWIzYzQgXHVjNzc0XHViN2YwIFx1YzBhY1x1YzJlNFx1YzVkMCBcdWM1NDhcdWQwYzBcdWFlNGNcdWM2YzBcdWM3NDQgXHViMjkwXHVhZjA4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWNmY1x1YzY3OCBcdWIxNzhcdWQyYjggXHVjNWM2XHViMjk0IFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBcdWQzYzlcdWJjOTRcdWQ1NWMgXHViMzAwXHVkNTU5XHVjMGRkXHVhY2ZjIFx1YWMxOVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNTQ0XHVjOWMxIFx1YjNjY1x1YzU0NFx1YWMwOCBcdWMyMTggXHVjNWM2XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZmNcdWM2NzggXHViMTc4XHVkMmI4XHVjNzU4IFx1YjJlOFx1YzExY1x1YjI5NCBcdWI3M2JcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzJhNFx1ZDM5OFx1Yzc3OFx1YzViNCBcdWFjZmNcdWM2NzhcdWI5N2MgXHViYzFiXHViMzU4IFx1YzkxMVx1YzVkMCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NTggXHVhY2ZjXHVjNjc4IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc3NCBcdWM4ZmNcdWI5ZDBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjRmMVx1YzBiMFx1Yzc0NCBcdWQ1NThcdWIzNTggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNlMFx1YjMwMCBcdWI5YzhcdWM1N2NcdWM3NTggXHVjMGFjXHVjNmQwXHVjNzNjXHViODVjIFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHVhY2UwLCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhY2ZjXHVjNjc4IFx1YjE3OFx1ZDJiOFx1YWMwMCBcdWFjNzBcdWFlMzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM4MyBcdWFjMTlcdWIyZTRcdWFjZTAgXHVjNTRjXHViODI0XHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjOTg5XHVjMmRjIFx1YWNmY1x1YzY3OCBcdWIxNzhcdWQyYjhcdWI5N2MgXHVjYzNlXHVjNzNjXHViN2VjIFx1YWNlMFx1YjMwMCBcdWI5YzhcdWM1N2NcdWM3NTggXHVjMGFjXHVjNmQwXHVjNzNjXHViODVjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI1YTBcdWIwYWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YjMwMCBcdWI5YzhcdWM1N2NcdWM3NTggXHVjMGFjXHVjNmQwXHVjNzU4IFx1Yzc4NVx1YWQ2Y1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDQgXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzQwIFx1YjllNFx1YzZiMCBcdWIxODBcdWI3OTBcdWIyZTQuIFx1YmMxNFx1Yjg1YyBcdWFjZmNcdWM2NzggXHViMTc4XHVkMmI4XHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWIyMDggXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjODMgXHVjNzc0XHVjNWM4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjNzc0XHVjODAxXHVjNzU4IFx1YjJlNFx1ZDU4OVx1Yzc3NFx1YjJlNFx1Yjk3YyBcdWJkODBcdWI5NzRcdWJhNzRcdWMxMWMgXHVhY2ZjXHVjNjc4IFx1YjE3OFx1ZDJiOFx1Yjk3YyBcdWM5ZDFcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWFjODNcdWM3NDAgXHViMTc4XHVkMmI4XHVjNzU4IFx1ZDY0MFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NFx1YzVjOFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YWNlMFx1YjMwMCBcdWI5YzhcdWM1N2NcdWM3NzhcdWM3NTggXHViYWE5XHVjMThjXHViOWFjXHVhYzAwIFx1YzBhY1x1YzZkMFx1Yzc0NCBcdWFjMDBcdWI0ZGQgXHVjYzQ0XHVjNmIwXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFjZTBcdWIzMDAgXHViOWM4XHVjNTdjXHVjNzc4XHVjNzQwIFx1YzJhNFx1ZDM5OFx1Yzc3OFx1YzViNFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHViMmU1XHVkMTMwXHVkNmM0XHVjNWQwXHVhYzhjIFx1YzgwNFx1ZDY1NFx1Yjk3YyBcdWFjNzhcdWM1YjRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNWQwXHVhYzhjIFx1ZDBjMFx1YjUxNFx1YzJhNFx1Yzc1OCBcdWJjODhcdWM1ZWQgXHVkNTA0XHViODVjXHVkMWEwXHVjZjVjXHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU3NCBcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWJiM2NcdWM1YjQgXHViY2Y0XHVjNTU4XHViMmU0LiBcdWIyZTVcdWQxMzBcdWIyOTQgXHVkNzU0XHVjZjhjXHVkNzg4IFx1YzY5NFx1Y2NhZFx1Yzc0NCBcdWJjMWJcdWM1NDRcdWI0ZTRcdWM2MDBcdWFjZTAsIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWI5YzhcdWM1N2NcdWM3NzhcdWM3NTggXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YjRlM1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHViYzE2XHVjNzNjXHViODVjIFx1YjA5OFx1YWMxNFx1YjJlNFx1YWMwMCBcdWIyZTRcdWMyZGMgXHViNGU0XHVjNWI0XHVjNjU0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtcdWQ1NThcdWQ1NThcdWQ1NTguIFx1YWNmY1x1YzY3OCBcdWIxNzhcdWQyYjhcdWI5N2MgXHViM2NjXHViODI0IFx1YmMxYlx1YWNlMCBcdWMyZjZcdWIwOTg/IFx1YWRmOFx1YjdmYyBcdWM1ZWNcdWFlMzBcdWI4NWMgXHVjNjQwXHVjMTFjIFx1YWMwMFx1YzgzOFx1YWMwMCBcdWJjZjRcdWMyZGNcdWM5YzAuIFx1ZDU1OFx1ZDU1OFx1ZDU1OFx1ZDU1OCZxdW90OzxcL3A+XHJcblxyXG48cD5cdWFjZmNcdWM2NzhcdWI5ZThcdWM3NTggXHVhY2ZjXHVjNjc4IFx1YjE3OFx1ZDJiOFx1YjI5NCBcdWM3ODVcdWFkNmNcdWM3NTggXHViYzE4XHViMzAwXHVkM2I4XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWM4MDhcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFjMTFcdWM3OTBcdWFlMzAgXHVkNTU4XHViMjk4XHVjNWQwXHVjMTFjIFx1YWM3MFx1YjMwMFx1ZDU1YyBcdWIzYzRcdWJiZjhcdWIxNzggXHVkMGMwXHVjNzdjXHVjNzc0IFx1YjVhOFx1YzViNFx1Yzg0Y1x1YWNlMCwgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViMmU0XHViOWFjXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViYmY4XHViMTc4IFx1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWI0NTAgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YzhcdWFjZTAsIFx1YWMwMSBcdWM4NzBcdWFjMDFcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiBcdWM4NzBcdWFjMDFcdWM1ZDBcdWIyOTQgMVx1YWNmYyA2XHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWMzNjhcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwYzBcdWM3N2NcdWM3NDAgTlx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWQ2NDBcdWMyMTggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzc0LCBcdWM5ZGRcdWMyMTggXHVjOTA0XHVjNWQwXHViMjk0IE4tMVx1YWMxY1x1Yzc1OCBcdWQwYzBcdWM3N2NcdWM3NzQgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCAoTj01KVx1Yzc3YyBcdWI1NGMgXHVkMGMwXHVjNzdjXHVjNzc0IFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzA0ZjM3YTdiLTIzMDgtNGYxYy04MzdhLWFkNTE5N2MxNDg3MFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzA0cHg7IGhlaWdodDogMTIycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWQwYzBcdWM3N2NcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWIxMThcdWM1YjRcdWFjMDBcdWI4MjRcdWJhNzQsIFx1YjQ1MCBcdWQwYzBcdWM3N2NcdWM3NzQgXHVjNzc4XHVjODExXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFjMTlcdWM3NDAgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YjI5NCBcdWM4NzBcdWFjMDFcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2ZjXHVjNjc4XHViOWU4XHVjNzQwIFx1YmMxOFx1YjMwMFx1ZDNiOFx1YzczY1x1Yjg1YyBcdWIxMThcdWM1YjRcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Y2NhYiBcdWM5MDRcdWM3NTggXHVhYzAwXHVjN2E1IFx1Y2NhYiBcdWQwYzBcdWM3N2NcdWM1ZDBcdWMxMWMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5IFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGMwXHVjNzdjXHVjNzQwIHJvdy1tYWpvciBvcmRlclx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzU4IFx1Y2NhYiBcdWQwYzBcdWM3N2NcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDEsIFx1YjljOFx1YzljMFx1YjljOSBcdWQwYzBcdWM3N2NcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IE5cdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWQwYzBcdWM3N2NcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IE4rMVx1Yzc3NFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMipOLTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWM5MDRcdWM3NTggXHVjY2FiIFx1ZDBjMFx1Yzc3Y1x1Yjg1Y1x1YjljYyBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NzQgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1ZDBjMFx1Yzc3Y1x1YzcwNFx1YzVkMCBcdWFjZmNcdWM2NzggXHViMTc4XHVkMmI4XHVhYzAwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViYzg4XHVkNjM4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVkMGMwXHVjNzdjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTipOLU5cLzJcdWM5MDQoXC9cdWIyOTQgXHVjODE1XHVjMjE4IFx1YjA5OFx1YjIxN1x1YzE0OFx1Yzc3NFx1YjJlNClcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzU5MVx1Yzc1OCBBPHN1Yj5pPFwvc3ViPlx1YzY0MCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgNiwgMSAmbGU7IGkgJmxlOyBOICogTiAtIE4gXC8gMikgXHVkMGMwXHVjNzdjIGlcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IEE8c3ViPmk8XC9zdWI+LCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWIyOTQgQjxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgKFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMTgpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNzU4IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhY2JkXHViODVjXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUyMTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUT1RFTSIsImRlc2NyaXB0aW9uIjoiPHA+TWlzdGVyIE5vIChyZWFsIG5hbWUgSmVycnkgRHJha2UpIGlzIGEgY29taWMgYm9vayBjaGFyYWN0ZXIgd2hvIGZyZXF1ZW50bHkgZ2V0cyBoaW1zZWxmIGludG8gYSBsb3Qgb2YgdHJvdWJsZSwgd2hpY2ggaGUgaXMgdXN1YWxseSBhYmxlIHRvIGdldCBvdXQgb2YuIEhvd2V2ZXIsIHRoaXMgdGltZSBpdCYjMzk7cyBub3Qgc28gZWFzeS4gSGUgd2FzIHNlYXJjaGluZyBmb3IgYW5jaWVudCBNYXlhbiB0cmVhc3VyZXMgYW5kLCBpbiB0aGUgcHJvY2Vzcywgc3R1bWJsZWQgdXBvbiBhIGxvc3QgdGVtcGxlLiBJbnNpZGUgdGhlIHRlbXBsZSB0aGVyZSBpcyBhIGxhcmdlIGhhbGwsIGFuZCBpbnNpZGUgdGhlIGhhbGwgc3RhbmRzIGEgc3RvbmUgVG90ZW0gd2l0aCBpbnNjcmlwdGlvbnMgdGhhdCBhcmUgdGhlIGtleSB0byB1bmRlcnN0YW5kaW5nIHRoZSBwdXJwb3NlIG9mIGxpZmUgKDQyKS4gSG93ZXZlciwgZ2V0dGluZyB0byB0aGUgVG90ZW0gaXMgYSBncmVhdCBjaGFsbGVuZ2UuPFwvcD5cclxuXHJcbjxwPlRoZSBUb3RlbSBpcyBzaXR1YXRlZCBvbiB0aGUgb3Bwb3NpdGUgc2lkZSBvZiB0aGUgaGFsbCBmb3JtIHRoZSBlbnRyYW5jZS4gVGhlIGZsb29yIG9mIHRoZSBoYWxsIGlzIGNvdmVyZWQgd2l0aCBzdG9uZSB0aWxlcyB0aGF0IGJlYXIgYSBzdHJpa2luZyByZXNlbWJsYW5jZSB0byBkb21pbm8gdGlsZXMuIEVhY2ggdGlsZSBpcyBkaXZpZGVkIGludG8gdHdvIGhhbHZlcyAoc3F1YXJlcyksIGFuZCBlYWNoIGhhbGYgaGFzIGEgbnVtYmVyIGZyb20gb25lIHRvIHNpeCwgaW5jbHVzaXZlLCBjaGlzZWxlZCBpbnRvIGl0LiBUaWxlcyBhcmUgYXJyYW5nZWQgaW4gTiByb3dzLCB3aXRoIE4gdGlsZXMgaW4gZWFjaCBvZGQtbnVtYmVyZWQgcm93IGFuZCBOIC0gMSB0aWxlcyBpbiBlYWNoIGV2ZW4tbnVtYmVyZWQgcm93LiBUaGUgaW1hZ2UgYmVsb3cgY29ycmVzcG9uZHMgdG8gdGhlIGZpcnN0IHRlc3QgZXhhbXBsZSAoTiA9IDUpOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzA0ZjM3YTdiLTIzMDgtNGYxYy04MzdhLWFkNTE5N2MxNDg3MFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzA0cHg7IGhlaWdodDogMTIycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkl0IGlzIG9ubHkgcG9zc2libGUgdG8gc3RlcCBmcm9tIG9uZSB0aWxlIHRvIGFuIGFkamFjZW50IG9uZSBpZiB0aGUgdHdvIHRpbGVzIGhhdmUgbWF0Y2hpbmcgbnVtYmVycyBvbiBoYWx2ZXMgdGhhdCBzaGFyZSBhbiBlZGdlLiBIZWxwIE1pc3RlciBObyBmaW5kIHRoZSBzaG9ydGVzdCBwYXRoIHRvIHRoZSBUb3RlbSBieSBkZXRlcm1pbmluZyB0aGUgc2VxdWVuY2Ugb2YgdGlsZXMgKG91dHB1dHRpbmcgdGhlIHNlcXVlbmNlIG9mIHRpbGVzJiMzOTsgbGFiZWxzLCBkZXNjcmliZWQgYmVsb3cpIHRoYXQgbmVlZCB0byBiZSBzdGVwcGVkIG9uLCBpbiBvcmRlciwgZnJvbSB0aGUgZmlyc3QgdG8gdGhlIGxhc3QgdGlsZSBvbiB0aGUgcGF0aC4gSWYgdGhlcmUgaXMgbm8gcG9zc2libGUgcGF0aCB0byB0aGUgVG90ZW0sIGZpbmQgdGhlIHNob3J0ZXN0IHBhdGggdG8gdGhlIHRpbGUgd2l0aCB0aGUgbGFyZ2VzdCBsYWJlbCAoc28gdGhhdCBNaXN0ZXIgTm8gY2FuIG1ha2UgYSBoZXJvaWMganVtcCkuIFRoZSBzdG9uZSB0aWxlcyBhcmUgbGFiZWxsZWQgaW4gcm93LW1ham9yIG9yZGVyOiBpbiB0aGUgZmlyc3Qgcm93LCB0aGUgZmlyc3QgdGlsZSBoYXMgdGhlIGxhYmVsIDEsIGFuZCB0aGUgbGFzdCBvbmUgTjsgaW4gdGhlIHNlY29uZCByb3csIHRoZSBmaXJzdCB0aWxlIGlzIE4gKyAxLCBhbmQgdGhlIGxhc3Qgb25lIDIqTiAtIDEsIGFuZCBzbyBvbi4gVGhlIGVudHJhbmNlIGxlYWRzIHRvIHRoZSB0aWxlIHdpdGggbGFiZWwgMSwgYW5kIHRoZSB0b3RlbSBpcyBvbiB0aGUgbGFzdCB0aWxlIGluIHRoZSBsYXN0IHJvdy4gTWlzdGVyIE5vIGFsd2F5cyBzdGFydHMgZnJvbSB0aGUgZW50cmFuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwMCksIHRoZSBudW1iZXIgb2Ygc3RvbmUgdGlsZSByb3dzLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiAqIE4gLSBOIFwvIDIgbGluZXMgKHdoZXJlICZsZHF1bztcLyZyZHF1bzsgc3RhbmRzIGZvciBpbnRlZ2VyIGRpdmlzaW9uKSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgQTxzdWI+aTxcL3N1Yj4gYW5kIEI8c3ViPmk8XC9zdWI+ICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgNiwgMSAmbGU7IGkgJmxlOyBOICogTiAtIE4gXC8gMiksIHRoZSB2YWx1ZXMgY2hpc2VsZWQgaW50byB0aGUgbGVmdCBhbmQgcmlnaHQgaGFsdmVzLCByZXNwZWN0aXZlbHksIG9mIHRpbGUgaS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBsZW5ndGggKGluIHRpbGVzKSBvZiB0aGUgcmVxdWlyZWQgc2hvcnRlc3QgcGF0aC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBzZXF1ZW5jZSBvZiBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMsIHRoZSBsYWJlbHMgb2YgdGlsZXMgb24gdGhlIHNob3J0ZXN0IHBhdGguIEFzIHRoZXJlIGNhbiBleGlzdCBtb3JlIHRoYW4gb25lIHNob3J0ZXN0IHBhdGgsIG91dHB1dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 3번