시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 316 100 61 30.500%

문제

경기도의 어떤 한 도시는 새 구역을 건설해서 도시를 확장하려고 한다. 그래서 이 도시에서는 우리의 친구 남서를 비롯한 여러 유명 건축가들을 불러 디자인을 시켰다. 남서는 도로망 디자인 담당이 되었는데, 귀찮았던 나머지 구역 내의 지역들을 잇는 모든 도로를 일방통행으로 만들어버렸다. (다행히도, 두 지역 A B간에 A에서 B로 가는 도로, B에서 A로 가는 도로를 놓아 서로 연결할 수 있다.)

남서는 자신의 도로망 계획을 지도해 그려본 결과, 일방통행 도로들 때문에 몇몇 지역들에서 특정 지역으로 갈 수 없다는 것을 깨달았다. 이 문제를 해결하기 위해서, 남서는 놀라운 접근법을 사용하기로 했다: 종이에 갈 수 있는 모든 경우의 수를 쓰는 것이다. 좀 더 자세히 말하자면, 각 지역 j에 대해서 j로부터 갈 수 있는 모든 지역에 대해 리스트를 작성하는 것이다. 우리는 이 리스트를 도로망의 '갈 수 있는 지역 리스트'라고 부른다. (만약 A에서 B로 가는 길이, B에서 C로 가는 길이 있다면 A의 리스트에는 B,C가, B의 리스트에는 C가 적힐 것이다.)

그러나, 남서는 문제를 해결하던 도중 하드 디스크가 망가져 자기가 만든 도로망 계획을 모두 잃어버렸다. 그에게 남은 것은 책상 위의 종이 한 장 - '갈 수 있는 지역 리스트' 하나 뿐이다.

우리는 불쌍한 남서를 도와 이 '갈 수 있는 리스트'를 통해서 원래 도로망 계획을 알아내려고 한다. 물론, 한 '갈 수 있는 리스트'에 대해서 여러 도로망 구조가 만들어질 수 있다. 우리는 이 중에서 각 지역을 잇는 도로의 개수가 가장 적은 도로망 계획을 구하고자 한다. 그러면 아마도 남서에게 큰 도움이 될 것이다.

주어진 '갈 수 있는 지역 리스트'에 대해서 가장 적은 도로로 이루어진 도로망 계획을 구하여라.

입력

첫 라인에는 전체 테스트 케이스의 개수 t 가 주어진다. 각 테스트 케이스는 빈 줄로 구분된다.

각 테스트 케이스의 첫 줄에는 지역의 개수를 나타내는 수 n (1 ≤ n ≤ 300)이 주어진다. 각 지역은 1부터 n까지 번호가 부여되어있다. 그 다음 n줄은 각각 길이 n의 문자열이 주어진다. 각 i번째 줄은 지역 i로부터 갈 수 있는 지역들에 대한 정보를 나타낸다. 정확하게 말하자면, j번째 문자가 0이라면 지역 i에서 j로 갈 수 없는 것이고, j번째 문자가 1이라면 지역 i에서 j로 가는 방법이 하나 이상 존재하는 것이다. (물론, 지역 i에서 i로는 항상 갈 수 있다.)

주어진 '갈 수 있는 지역 리스트'는 실제로 하나 이상의 도로망을 구성할 수 있다.

출력

각 테스트 케이스에 대해서, 가장 적은 도로로 이루어진 도로망 계획을 구한다. 첫 번째 줄에는 도로의 개수 m (물론, 이 m은 가능한 한 작아야 한다!)이 주어진다. 그리고 그 뒤로 이어지는 m개의 줄에는 두 개의 수 ai and bi (1 ≤ ai, bi ≤ n)을 출력한다. 이는 지역 ai 에서 bi로 가는 도로를 의미한다.

도로는 어떤 순서로 출력해도 상관 없다. 만약 하나 이상의 해가 존재한다면 그 중 어떤 것을 출력해도 문제 없다.

예제 입력 1

2

3
111
011
001

4
1111
1111
0011
0011

예제 출력 1

2
1 2
2 3

5
1 2
2 1
1 3
3 4
4 3
W3sicHJvYmxlbV9pZCI6IjExMDk3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHVjMmRjIFx1YWNjNFx1ZDY4ZCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhY2JkXHVhZTMwXHViM2M0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWQ1NWMgXHViM2M0XHVjMmRjXHViMjk0IFx1YzBjOCBcdWFkNmNcdWM1ZWRcdWM3NDQgXHVhYzc0XHVjMTI0XHVkNTc0XHVjMTFjIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWQ2NTVcdWM3YTVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNzc0IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM2YjBcdWI5YWNcdWM3NTggXHVjZTVjXHVhZDZjIFx1YjBhOFx1YzExY1x1Yjk3YyBcdWJlNDRcdWI4NmZcdWQ1NWMgXHVjNWVjXHViN2VjIFx1YzcyMFx1YmE4NSBcdWFjNzRcdWNkOTVcdWFjMDBcdWI0ZTRcdWM3NDQgXHViZDg4XHViN2VjIFx1YjUxNFx1Yzc5MFx1Yzc3OFx1Yzc0NCBcdWMyZGNcdWNmMzBcdWIyZTQuIFx1YjBhOFx1YzExY1x1YjI5NCBcdWIzYzRcdWI4NWNcdWI5ZGQgXHViNTE0XHVjNzkwXHVjNzc4IFx1YjJmNFx1YjJmOVx1Yzc3NCBcdWI0MThcdWM1YzhcdWIyOTRcdWIzNzAsJm5ic3A7XHVhZGMwXHVjYzJlXHVjNTU4XHViMzU4IFx1YjA5OFx1YmEzOFx1YzljMCBcdWFkNmNcdWM1ZWQgXHViMGI0XHVjNzU4IFx1YzljMFx1YzVlZFx1YjRlNFx1Yzc0NCBcdWM3ODdcdWIyOTQmbmJzcDtcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViOTdjIFx1Yzc3Y1x1YmMyOVx1ZDFiNVx1ZDU4OVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWJjODRcdWI4MzhcdWIyZTQuIChcdWIyZTRcdWQ1ODlcdWQ3ODhcdWIzYzQsIFx1YjQ1MCBcdWM5YzBcdWM1ZWQmbmJzcDtBIEJcdWFjMDRcdWM1ZDAgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWIzYzRcdWI4NWMsIEJcdWM1ZDBcdWMxMWMgQVx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1YjE5M1x1YzU0NCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTYwJm5ic3A7XHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YjBhOFx1YzExY1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHViM2M0XHViODVjXHViOWRkIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWM5YzBcdWIzYzRcdWQ1NzQgXHVhZGY4XHViODI0XHViY2Y4IFx1YWNiMFx1YWNmYywgXHVjNzdjXHViYzI5XHVkMWI1XHVkNTg5IFx1YjNjNFx1Yjg1Y1x1YjRlNCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYTg3XHViYTg3Jm5ic3A7XHVjOWMwXHVjNWVkXHViNGU0XHVjNWQwXHVjMTFjJm5ic3A7XHVkMmI5XHVjODE1IFx1YzljMFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTY4XHViMmVjXHVjNTU4XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1YjBhOFx1YzExY1x1YjI5NCBcdWIxODBcdWI3N2NcdWM2YjQgXHVjODExXHVhZGZjXHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQ6IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAmbmJzcDtcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YzRmMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzg4MCBcdWIzNTQgXHVjNzkwXHVjMTM4XHVkNzg4Jm5ic3A7XHViOWQwXHVkNTU4XHVjNzkwXHViYTc0LCBcdWFjMDEgXHVjOWMwXHVjNWVkIGpcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIGpcdWI4NWNcdWJkODBcdWQxMzAgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQmbmJzcDtcdWJhYThcdWI0ZTAgXHVjOWMwXHVjNWVkXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1Yzc3NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWI5N2MgXHViM2M0XHViODVjXHViOWRkXHVjNzU4Jm5ic3A7JiMzOTtcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzBcdWM1ZWQmbmJzcDtcdWI5YWNcdWMyYTRcdWQyYjgmIzM5O1x1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuIChcdWI5Y2NcdWM1N2QgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWFlMzhcdWM3NzQsIEJcdWM1ZDBcdWMxMWMgQ1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCBBXHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMFx1YjI5NCBCLENcdWFjMDAsIEJcdWM3NTggXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHViMjk0IENcdWFjMDAgXHVjODAxXHVkNzkwIFx1YWM4M1x1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjA5OCwmbmJzcDtcdWIwYThcdWMxMWNcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YjM1OCBcdWIzYzRcdWM5MTEmbmJzcDtcdWQ1NThcdWI0ZGMgXHViNTE0XHVjMmE0XHVkMDZjXHVhYzAwIFx1YjlkZFx1YWMwMFx1YzgzOCBcdWM3OTBcdWFlMzBcdWFjMDAgXHViOWNjXHViNGUwIFx1YjNjNFx1Yjg1Y1x1YjlkZCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHViYWE4XHViNDUwIFx1Yzc4M1x1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVhZGY4XHVjNWQwXHVhYzhjIFx1YjBhOFx1Yzc0MCBcdWFjODNcdWM3NDAgXHVjYzQ1XHVjMGMxIFx1YzcwNFx1Yzc1OCBcdWM4ODVcdWM3NzQgXHVkNTVjIFx1YzdhNSAtICYjMzk7XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWMwXHVjNWVkJm5ic3A7XHViOWFjXHVjMmE0XHVkMmI4JiMzOTsgXHVkNTU4XHViMDk4IFx1YmZkMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YmQ4OFx1YzMwZFx1ZDU1YyBcdWIwYThcdWMxMWNcdWI5N2MgXHViM2M0XHVjNjQwIFx1Yzc3NCAmIzM5O1x1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjlhY1x1YzJhNFx1ZDJiOCYjMzk7XHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM2ZDBcdWI3OTggXHViM2M0XHViODVjXHViOWRkIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAsIFx1ZDU1YyAmIzM5O1x1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjlhY1x1YzJhNFx1ZDJiOCYjMzk7XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM1ZWNcdWI3ZWMgXHViM2M0XHViODVjXHViOWRkIFx1YWQ2Y1x1Yzg3MFx1YWMwMCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1Yzc3NCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1YzljMFx1YzVlZFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YjlkZCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVhZDZjXHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHViYTc0IFx1YzU0NFx1YjljOFx1YjNjNCZuYnNwO1x1YjBhOFx1YzExY1x1YzVkMFx1YWM4YyBcdWQwNzAgXHViM2M0XHVjNmMwXHVjNzc0IFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCAmIzM5O1x1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZCBcdWI5YWNcdWMyYTRcdWQyYjgmIzM5O1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjNjNFx1Yjg1Y1x1YjlkZCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1Yjc3Y1x1Yzc3OFx1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWM1ZWRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMTggbiZuYnNwOygxICZsZTsgbiAmbGU7IDMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOWMwXHVjNWVkXHVjNzQwIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIG5cdWM5MDRcdWM3NDAgXHVhYzAxXHVhYzAxJm5ic3A7XHVhZTM4XHVjNzc0IG5cdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YzljMFx1YzVlZCBpXHViODVjXHViZDgwXHVkMTMwIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YjlkMFx1ZDU1OFx1Yzc5MFx1YmE3NCwgalx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWFjMDAgMFx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWM5YzBcdWM1ZWQgaVx1YzVkMFx1YzExYyBqXHViODVjIFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgalx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWFjMDAgMVx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWM5YzBcdWM1ZWQgaVx1YzVkMFx1YzExYyBqXHViODVjIFx1YWMwMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAoXHViYjNjXHViODYwLCBcdWM5YzBcdWM1ZWQgaVx1YzVkMFx1YzExYyBpXHViODVjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCAmIzM5O1x1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZCBcdWI5YWNcdWMyYTRcdWQyYjgmIzM5O1x1YjI5NCBcdWMyZTRcdWM4MWNcdWI4NWMmbmJzcDtcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjlkZFx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIzYzRcdWI4NWNcdWI5ZGQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YWQ2Y1x1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOCBtIChcdWJiM2NcdWI4NjAsIFx1Yzc3NCBtXHVjNzQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjNzkxXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNCEpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWI0YTRcdWI4NWMgXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMjE4Jm5ic3A7YTxzdWI+aTxcL3N1Yj4mbmJzcDthbmQgYjxzdWI+aTxcL3N1Yj4mbmJzcDsoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgbilcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjOWMwXHVjNWVkIGE8c3ViPmk8XC9zdWI+IFx1YzVkMFx1YzExYyBiPHN1Yj5pPFwvc3ViPlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViODVjXHViMjk0IFx1YzViNFx1YjVhNCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjZDljXHViODI1XHVkNTc0XHViM2M0IFx1YzBjMVx1YWQwMCBcdWM1YzZcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDU3NFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWM1YjRcdWI1YTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWJiMzhcdWM4MWMgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMDk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVXJiYW4gcGxhbm5pbmciLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB0b3duIG9mIFBlemlub2sgd2FudHMgdG8gZXhwYW5kIGJ5IGJ1aWxkaW5nIGEgbmV3IG5laWdoYm9yaG9vZC4gVGhleSBoaXJlZCBzb21lIGZhbW91cyBhcmNoaXRlY3RzIHRvIGRlc2lnbiBpdCwgYW5kIHlvdXIgZnJpZW5kIEphbm8gaXMgb25lIG9mIHRoZW0uIEhlIGlzIGluIGNoYXJnZSBvZiB0aGUgcm9hZCBuZXR3b3JrLiBJdCBpcyBjb21tb24gdG8gbWFrZSBvbmUtd2F5IHJvYWRzIHRoZXNlIGRheXMsIHNvIEphbm8gd2VudCBhbGwgb3V0IGFuZCBkZWNpZGVkIHRvIG1ha2UgYWxsIHRoZSByb2FkcyBvbmUtd2F5LiAoT2YgY291cnNlLCBhIHBhaXIgb2YganVuY3Rpb25zIGNhbiBiZSBjb25uZWN0ZWQgYnkgdHdvIHJvYWRzICZuZGFzaDsgb25lIGluIGVhY2ggZGlyZWN0aW9uLik8XC9wPlxyXG5cclxuPHA+T25jZSBKYW5vIG1hZGUgYSBtYXAgc2hvd2luZyB0aGUgcGxhbm5lZCByb2FkcywgaGUgbm90aWNlZCB0aGF0IHNvbWUgcGFydHMgb2YgdGhlIG5laWdoYm9yaG9vZCBtaWdodCBub3QgYmUgcmVhY2hhYmxlIGZyb20gb3RoZXIgcGFydHMuIFRvIGVzdGltYXRlIHRoZSBpbXBhY3Qgb2YgdGhpcyBpc3N1ZSwgaGUgZGVjaWRlZCB0byB1c2UgYSBzeXN0ZW1hdGljIGFwcHJvYWNoOiBoZSB0b29rIGEgcGllY2Ugb2YgcGFwZXIgYW5kIHdyb3RlIGV2ZXJ5dGhpbmcgZG93bi4gTmFtZWx5LCBmb3IgZWFjaCBqdW5jdGlvbiBqIGhlIGxpc3RlZCBhbGwgb3RoZXIganVuY3Rpb25zIHRoYXQgYXJlIChkaXJlY3RseSBvciBpbmRpcmVjdGx5KSByZWFjaGFibGUgZnJvbSBqLiBXZSBjYWxsIHRoaXMgaW5mb3JtYXRpb24gdGhlIHJlYWNoYWJpbGl0eSBsaXN0IG9mIGEgcm9hZCBuZXR3b3JrLjxcL3A+XHJcblxyXG48cD5CdXQgdGhlbiBKYW5vJnJzcXVvO3MgaGFyZCBkcml2ZSBjcmFzaGVkIGFuZCBoZSBsb3N0IGFsbCB0aGUgcGxhbnMgaGUgaGFkIG1hZGUuIFRoZSBvbmx5IHRoaW5nIGhlIGhhcyBsZWZ0IGlzIHRoZSBwaWVjZSBvZiBwYXBlciB3aXRoIHRoZSByZWFjaGFiaWxpdHkgbGlzdC48XC9wPlxyXG5cclxuPHA+SGVscCBKYW5vIHJlY29uc3RydWN0IGhpcyBvcmlnaW5hbCByb2FkIG5ldHdvcmsuIE9mIGNvdXJzZSwgbWFueSBkaWZmZXJlbnQgcm9hZCBuZXR3b3JrcyBjYW4gcHJvZHVjZSB0aGUgc2FtZSByZWFjaGFiaWxpdHkgbGlzdC4gVGhlcmVmb3JlLCBKYW5vIGFza2VkIHlvdSB0byBmaW5kIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSByb2FkIG5ldHdvcmsgdGhhdCBoYXMgdGhlIGdpdmVuIHJlYWNoYWJpbGl0eSBsaXN0LiBUaGF0IHNob3VsZCBoZWxwIGhpbSByZWNvbnN0cnVjdCBoaXMgb3JpZ2luYWwgcGxhbnMuPFwvcD5cclxuXHJcbjxwPkZpbmQgYSByb2FkIG5ldHdvcmsgd2l0aCB0aGUgc21hbGxlc3QgcG9zc2libGUgbnVtYmVyIG9mIHJvYWRzIHRoYXQgaGFzIHRoZSBnaXZlbiByZWFjaGFiaWxpdHkgbGlzdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIGFuIGludGVnZXIgdCBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgcHJlY2VkZWQgYnkgYSBibGFuayBsaW5lLjxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMzAwKSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBqdW5jdGlvbnMuIFRoZSBqdW5jdGlvbnMgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBuLiBOZXh0LCBuIGxpbmVzIGZvbGxvdywgZWFjaCBjb250YWluaW5nIGEgc3RyaW5nIG9mIGxlbmd0aCBuLiBUaGUgaS10aCBvZiB0aGVzZSBsaW5lcyBzcGVjaWZpZXMgd2hpY2gganVuY3Rpb25zIGFyZSByZWFjaGFibGUgZnJvbSBqdW5jdGlvbiBpLiBOYW1lbHksIHRoZSBqLXRoIGNoYXJhY3RlciBpbiB0aGUgbGluZSBpcyAxIGlmIGp1bmN0aW9uIGogaXMgcmVhY2hhYmxlIGZyb20gaSBhbmQgMCBvdGhlcndpc2UuIChOb3RlIHRoYXQgZm9yIGVhY2ggaSwganVuY3Rpb24gaSBpcyByZWFjaGFibGUgZnJvbSBpdHNlbGYuKTxcL3A+XHJcblxyXG48cD5UaGUgcmVhY2hhYmlsaXR5IGxpc3QgaXMgY29uc2lzdGVudCAmbmRhc2g7IGl0IGRlc2NyaWJlcyBhdCBsZWFzdCBvbmUgcmVhbCByb2FkIG5ldHdvcmsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHNtYWxsZXN0IHJvYWQgbmV0d29yayB0aGF0IGNvcnJlc3BvbmRzIHRvIHRoZSBnaXZlbiByZWFjaGFiaWxpdHkgbGlzdC4gVGhlIGZpcnN0IGxpbmUgb2YgdGhlIGRlc2NyaXB0aW9uIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2Ygcm9hZHMgbSAod2hpY2ggaGFzIHRvIGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlKS4gRWFjaCBvZiB0aGUgbmV4dCBtIGxpbmVzIHNob3VsZCBjb250YWluIHR3byBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiZuYnNwO2FuZCBiPHN1Yj5pPFwvc3ViPiZuYnNwOygxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBuKSBzdWNoIHRoYXQgdGhlcmUgaXMgYSBvbmUtd2F5IHJvYWQgZ29pbmcgZnJvbSBqdW5jdGlvbiBhPHN1Yj5pPFwvc3ViPiZuYnNwO3RvIGp1bmN0aW9uIGI8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIHByaW50IHRoZSByb2FkcyBpbiBhbnkgb3JkZXIuIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBvcHRpbWFsIHNvbHV0aW9ucywgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Internet Problem Solving Contest > IPSC 2014 U번

  • 문제를 번역한 사람: jhs7jhs