시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB115835923428.925%

문제

경기도의 어떤 한 도시는 새 구역을 건설해서 도시를 확장하려고 한다. 그래서 이 도시에서는 우리의 친구 남서를 비롯한 여러 유명 건축가들을 불러 디자인을 시켰다. 남서는 도로망 디자인 담당이 되었는데, 귀찮았던 나머지 구역 내의 지역들을 잇는 모든 도로를 일방통행으로 만들어버렸다. (다행히도, 두 지역 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와 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+aTxcL3N1Yj5cdWM2NDAmbmJzcDtiPHN1Yj5pPFwvc3ViPiZuYnNwOygxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBuKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWM5YzBcdWM1ZWQgYTxzdWI+aTxcL3N1Yj4gXHVjNWQwXHVjMTFjIGI8c3ViPmk8XC9zdWI+XHViODVjIFx1YWMwMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWI4NWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWIzYzQgXHVjMGMxXHVhZDAwIFx1YzVjNlx1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHVkNTc0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjggXHVjOTExIFx1YzViNFx1YjVhNCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHViM2M0IFx1YmIzOFx1YzgxYyBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTEwOTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJVcmJhbiBwbGFubmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHRvd24gb2YgUGV6aW5vayB3YW50cyB0byBleHBhbmQgYnkgYnVpbGRpbmcgYSBuZXcgbmVpZ2hib3Job29kLiBUaGV5IGhpcmVkIHNvbWUgZmFtb3VzIGFyY2hpdGVjdHMgdG8gZGVzaWduIGl0LCBhbmQgeW91ciBmcmllbmQgSmFubyBpcyBvbmUgb2YgdGhlbS4gSGUgaXMgaW4gY2hhcmdlIG9mIHRoZSByb2FkIG5ldHdvcmsuIEl0IGlzIGNvbW1vbiB0byBtYWtlIG9uZS13YXkgcm9hZHMgdGhlc2UgZGF5cywgc28gSmFubyB3ZW50IGFsbCBvdXQgYW5kIGRlY2lkZWQgdG8gbWFrZSBhbGwgdGhlIHJvYWRzIG9uZS13YXkuIChPZiBjb3Vyc2UsIGEgcGFpciBvZiBqdW5jdGlvbnMgY2FuIGJlIGNvbm5lY3RlZCBieSB0d28gcm9hZHMgJm5kYXNoOyBvbmUgaW4gZWFjaCBkaXJlY3Rpb24uKTxcL3A+XHJcblxyXG48cD5PbmNlIEphbm8gbWFkZSBhIG1hcCBzaG93aW5nIHRoZSBwbGFubmVkIHJvYWRzLCBoZSBub3RpY2VkIHRoYXQgc29tZSBwYXJ0cyBvZiB0aGUgbmVpZ2hib3Job29kIG1pZ2h0IG5vdCBiZSByZWFjaGFibGUgZnJvbSBvdGhlciBwYXJ0cy4gVG8gZXN0aW1hdGUgdGhlIGltcGFjdCBvZiB0aGlzIGlzc3VlLCBoZSBkZWNpZGVkIHRvIHVzZSBhIHN5c3RlbWF0aWMgYXBwcm9hY2g6IGhlIHRvb2sgYSBwaWVjZSBvZiBwYXBlciBhbmQgd3JvdGUgZXZlcnl0aGluZyBkb3duLiBOYW1lbHksIGZvciBlYWNoIGp1bmN0aW9uIGogaGUgbGlzdGVkIGFsbCBvdGhlciBqdW5jdGlvbnMgdGhhdCBhcmUgKGRpcmVjdGx5IG9yIGluZGlyZWN0bHkpIHJlYWNoYWJsZSBmcm9tIGouIFdlIGNhbGwgdGhpcyBpbmZvcm1hdGlvbiB0aGUgcmVhY2hhYmlsaXR5IGxpc3Qgb2YgYSByb2FkIG5ldHdvcmsuPFwvcD5cclxuXHJcbjxwPkJ1dCB0aGVuIEphbm8mcnNxdW87cyBoYXJkIGRyaXZlIGNyYXNoZWQgYW5kIGhlIGxvc3QgYWxsIHRoZSBwbGFucyBoZSBoYWQgbWFkZS4gVGhlIG9ubHkgdGhpbmcgaGUgaGFzIGxlZnQgaXMgdGhlIHBpZWNlIG9mIHBhcGVyIHdpdGggdGhlIHJlYWNoYWJpbGl0eSBsaXN0LjxcL3A+XHJcblxyXG48cD5IZWxwIEphbm8gcmVjb25zdHJ1Y3QgaGlzIG9yaWdpbmFsIHJvYWQgbmV0d29yay4gT2YgY291cnNlLCBtYW55IGRpZmZlcmVudCByb2FkIG5ldHdvcmtzIGNhbiBwcm9kdWNlIHRoZSBzYW1lIHJlYWNoYWJpbGl0eSBsaXN0LiBUaGVyZWZvcmUsIEphbm8gYXNrZWQgeW91IHRvIGZpbmQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIHJvYWQgbmV0d29yayB0aGF0IGhhcyB0aGUgZ2l2ZW4gcmVhY2hhYmlsaXR5IGxpc3QuIFRoYXQgc2hvdWxkIGhlbHAgaGltIHJlY29uc3RydWN0IGhpcyBvcmlnaW5hbCBwbGFucy48XC9wPlxyXG5cclxuPHA+RmluZCBhIHJvYWQgbmV0d29yayB3aXRoIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBudW1iZXIgb2Ygcm9hZHMgdGhhdCBoYXMgdGhlIGdpdmVuIHJlYWNoYWJpbGl0eSBsaXN0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgYW4gaW50ZWdlciB0IHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBwcmVjZWRlZCBieSBhIGJsYW5rIGxpbmUuPFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAzMDApLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIGp1bmN0aW9ucy4gVGhlIGp1bmN0aW9ucyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIG4uIE5leHQsIG4gbGluZXMgZm9sbG93LCBlYWNoIGNvbnRhaW5pbmcgYSBzdHJpbmcgb2YgbGVuZ3RoIG4uIFRoZSBpLXRoIG9mIHRoZXNlIGxpbmVzIHNwZWNpZmllcyB3aGljaCBqdW5jdGlvbnMgYXJlIHJlYWNoYWJsZSBmcm9tIGp1bmN0aW9uIGkuIE5hbWVseSwgdGhlIGotdGggY2hhcmFjdGVyIGluIHRoZSBsaW5lIGlzIDEgaWYganVuY3Rpb24gaiBpcyByZWFjaGFibGUgZnJvbSBpIGFuZCAwIG90aGVyd2lzZS4gKE5vdGUgdGhhdCBmb3IgZWFjaCBpLCBqdW5jdGlvbiBpIGlzIHJlYWNoYWJsZSBmcm9tIGl0c2VsZi4pPFwvcD5cclxuXHJcbjxwPlRoZSByZWFjaGFiaWxpdHkgbGlzdCBpcyBjb25zaXN0ZW50ICZuZGFzaDsgaXQgZGVzY3JpYmVzIGF0IGxlYXN0IG9uZSByZWFsIHJvYWQgbmV0d29yay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgc21hbGxlc3Qgcm9hZCBuZXR3b3JrIHRoYXQgY29ycmVzcG9uZHMgdG8gdGhlIGdpdmVuIHJlYWNoYWJpbGl0eSBsaXN0LiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgZGVzY3JpcHRpb24gc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiByb2FkcyBtICh3aGljaCBoYXMgdG8gYmUgYXMgc21hbGwgYXMgcG9zc2libGUpLiBFYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgc2hvdWxkIGNvbnRhaW4gdHdvIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+Jm5ic3A7YW5kIGI8c3ViPmk8XC9zdWI+Jm5ic3A7KDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IG4pIHN1Y2ggdGhhdCB0aGVyZSBpcyBhIG9uZS13YXkgcm9hZCBnb2luZyBmcm9tIGp1bmN0aW9uIGE8c3ViPmk8XC9zdWI+Jm5ic3A7dG8ganVuY3Rpb24gYjxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gcHJpbnQgdGhlIHJvYWRzIGluIGFueSBvcmRlci4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIG9wdGltYWwgc29sdXRpb25zLCBvdXRwdXQgYW55IG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Internet Problem Solving Contest > IPSC 2014 U번

  • 문제를 번역한 사람: jhs7jhs