시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 128 MB112302827.723%

문제

원숭이와 멍멍이는 보드게임을 하고 있다. 보드판은 여러개의 위치로 나뉘며 각 위치는 알파벳 소문자 1개 (a, b, c, d, ...) 로 이름이 붙여져 있고, 게임말을 사용해 현재 위치를 표시한다. 이 게임은 매 라운드마다 다음과 같은 2개의 과정을 거친다.

  1. 원숭이가 선택을 한다. 게임말의 현재 위치에 따라 원숭이가 고를 수 있는 선택지들이 정해지고, 그 중의 하나를 선택해야 한다. 선택지는 보드판 위의 위치들의 집합이다.
  2. 멍멍이가 선택을 한다. 멍멍이는 첫 번째 과정에서 원숭이가 선택한 선택지 안에 있는 위치들 중에서 하나를 선택한 후 게임말을 그 위치로 움직인다. 이 위치가 다음 라운드의 위치가 된다.

첫 번째 라운드를 시작하기 전에, 원숭이와 멍멍이는 각각 위치를 하나 고른다. 멍멍이가 고른 위치는 게임말의 시작위치가 된다. 원숭이가 고른 위치는 게임이 끝나는 위치가 된다. 원숭이는 멍멍이가 움직이는 게임말을 자기가 고른 위치에 오도록 만들면 승리한다. 더 스릴넘치는 게임을 위해 두 사람은 돈을 걸고 플레이한다. 원숭이가 이기면 멍멍이는 원숭이에게 전재산을 주어야 한다. 하지만 원숭이는 매 라운드가 끝날 때 마다 멍멍이에게 일정 금액을 주어야 한다. 따라서 이 게임은 원숭이가 게임말을 끝위치로 오게 만들어 원숭이가 승리하든지, 아니면 원숭이의 돈이 다 떨어져서 패가망신하든지 둘 중 하나로 끝나게 된다.

원숭이와 멍멍이는 항상 최적의 전략으로 게임을 플레이한다. 원숭이는 항상 게임을 이기는 쪽으로 선택을 하고, 멍멍이는 원숭이가 이기는 것을 막도록 노력한다.

원숭이는 모든 경우의 시작위치와 끝위치에 대해서 자기가 게임을 이길 수 있는지, 이길 수 있다면 몇 라운드만에 이길 수 있는지 알고 싶어졌다.

입력

입력으로 한 개의 테스트케이스가 주어진다. 첫 번째 줄에는 보드판 위의 위치의 개수 n (1 ≤ n ≤ 25) 이 주어진다. n개 위치의 이름은 알파벳 소문자 중 처음 n개를 사용한다. 나머지 n개의 줄에는 각 위치 p에 대한 정보가 위치를 나타내는 알파벳 순으로 주어진다. 각 줄의 처음에는 선택지의 개수 m (1 ≤ m < 2n) 이 주어지고, 그 뒤로 m개의 중복되지 않는 문자열이 주어진다. 각 문자열은 하나의 선택지를 나타내며 멍멍이가 선택할 수 있는 위치들을 담고 있다. 문자열의 길이는 1 이상이며 각 글자는 알파벳 순으로 정렬되어 주어지고, 중복되는 글자는 없다. 테스트 케이스에 주어지는 선택지 개수의 합은 최대 106 이다.

출력

위치를 나타내는 알파벳 순으로 각 위치 p에 대해 한 줄을 출력한다. 각 줄 마다 위치를 나타내는 알파벳 순으로 각 위치 q에 대해 시작위치가 p이고 끝위치가 q인 게임을 원숭이가 이길 수 있는 최소 라운드 수를 출력한다. 원숭이가 패가망신하는 경우엔 -1을 출력한다.

예제 입력 1

2
2 ab b
1 b

예제 출력 1

0 1
-1 0
W3sicHJvYmxlbV9pZCI6IjEwMDUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTQ0XHVjMmI5IFx1YzgwNFx1YjdiNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNmQwXHVjMjJkXHVjNzc0XHVjNjQwIFx1YmE0ZFx1YmE0ZFx1Yzc3NFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHVkMzEwXHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI4NWMgXHViMDk4XHViMjU4XHViYTcwIFx1YWMwMSBcdWM3MDRcdWNlNThcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCAxXHVhYzFjIChhLCBiLCBjLCBkLCAuLi4pIFx1Yjg1YyBcdWM3NzRcdWI5ODRcdWM3NzQgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YWNlMCwmbmJzcDtcdWFjOGNcdWM3ODRcdWI5ZDBcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0IFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWI5N2MgXHVkNDVjXHVjMmRjXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjllNCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWI5YzhcdWIyZTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCAyXHVhYzFjXHVjNzU4IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNlNWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzEyMFx1ZDBkZFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1YjlkMFx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVhY2UwXHViOTdjJm5ic3A7XHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWQwZGRcdWM5YzBcdWI0ZTRcdWM3NzQmbmJzcDtcdWM4MTVcdWQ1NzRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWM5MTFcdWM3NTggXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1ZDBkZFx1YzljMFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWQzMTAgXHVjNzA0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmE0ZFx1YmE0ZFx1Yzc3NFx1YWMwMCBcdWMxMjBcdWQwZGRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWJhNGRcdWJhNGRcdWM3NzRcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMjBcdWQwZGRcdWM5YzAgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVkNmM0Jm5ic3A7XHVhYzhjXHVjNzg0XHViOWQwXHVjNzQ0IFx1YWRmOCBcdWM3MDRcdWNlNThcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LiBcdWM3NzQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjJlNFx1Yzc0YyBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwLCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM2NDAgXHViYTRkXHViYTRkXHVjNzc0XHViMjk0IFx1YWMwMVx1YWMwMSBcdWM3MDRcdWNlNThcdWI5N2MgXHVkNTU4XHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHViYTRkXHViYTRkXHVjNzc0XHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVhYzhjXHVjNzg0XHViOWQwXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzcwNFx1Y2U1OFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWFjZTBcdWI5NzggXHVjNzA0XHVjZTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjQxY1x1YjJlNC4mbmJzcDtcdWM2ZDBcdWMyMmRcdWM3NzRcdWIyOTQgXHViYTRkXHViYTRkXHVjNzc0XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWI5ZDBcdWM3NDQgXHVjNzkwXHVhZTMwXHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNjI0XHViM2M0XHViODVkJm5ic3A7XHViOWNjXHViNGU0XHViYTc0IFx1YzJiOVx1YjlhY1x1ZDU1Y1x1YjJlNC4gXHViMzU0IFx1YzJhNFx1YjliNFx1YjExOFx1Y2U1OFx1YjI5NCZuYnNwO1x1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWIzYzhcdWM3NDQgXHVhYzc4XHVhY2UwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTMwXHViYTc0IFx1YmE0ZFx1YmE0ZFx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjODA0XHVjN2FjXHVjMGIwXHVjNzQ0IFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWIyOTQgXHViOWU0IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YWMwMCBcdWIwNWRcdWIwYTAgXHViNTRjJm5ic3A7XHViOWM4XHViMmU0IFx1YmE0ZFx1YmE0ZFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM3N2NcdWM4MTUgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWFjOGNcdWM3ODRcdWI5ZDBcdWM3NDQgXHViMDVkXHVjNzA0XHVjZTU4XHViODVjIFx1YzYyNFx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzJiOVx1YjlhY1x1ZDU1OFx1YjRlMFx1YzljMCwgXHVjNTQ0XHViMmM4XHViYTc0IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWIzYzhcdWM3NzQgXHViMmU0IFx1YjVhOFx1YzViNFx1YzgzOFx1YzExYyBcdWQzMjhcdWFjMDBcdWI5ZGRcdWMyZTBcdWQ1NThcdWI0ZTBcdWM5YzAgXHViNDU4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHViMDVkXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmQwXHVjMjJkXHVjNzc0XHVjNjQwIFx1YmE0ZFx1YmE0ZFx1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzgwNFx1YjdiNVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTVjXHViMmU0LiBcdWM2ZDBcdWMyMmRcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxJm5ic3A7XHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWNhYmRcdWM3M2NcdWI4NWMgXHVjMTIwXHVkMGRkXHVjNzQ0IFx1ZDU1OFx1YWNlMCwgXHViYTRkXHViYTRkXHVjNzc0XHViMjk0IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjljOVx1YjNjNFx1Yjg1ZCBcdWIxNzhcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzcwNFx1Y2U1OFx1YzY0MCBcdWIwNWRcdWM3MDRcdWNlNThcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Yzc5MFx1YWUzMFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAsIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1YmE4NyBcdWI3N2NcdWM2YjRcdWI0ZGNcdWI5Y2NcdWM1ZDAgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YzViNFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyZuYnNwO1x1ZDU1YyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViY2Y0XHViNGRjXHVkMzEwIFx1YzcwNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4IG4mbmJzcDsoMSAmbGU7IG4gJmxlOyAyNSkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1YWMxYyZuYnNwO1x1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAmbmJzcDtcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIFx1YzkxMSBcdWNjOThcdWM3NGMgblx1YWMxY1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCZuYnNwO1x1YWMwMSBcdWM3MDRcdWNlNTggcFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQmbmJzcDtcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWFjMDEgXHVjOTA0XHVjNzU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWMxMjBcdWQwZGRcdWM5YzBcdWM3NTggXHVhYzFjXHVjMjE4IG0mbmJzcDsoMSAmbGU7IG0gJmx0OyAyPHN1cD5uPFwvc3VwPikgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhZGY4IFx1YjRhNFx1Yjg1YyBtXHVhYzFjXHVjNzU4IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMTIwXHVkMGRkXHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCBcdWJhNGRcdWJhNGRcdWM3NzRcdWFjMDAgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHViNGU0XHVjNzQ0IFx1YjJmNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMSBcdWM3NzRcdWMwYzFcdWM3NzRcdWJhNzAgXHVhYzAxIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjNWM2XHViMmU0LiZuYnNwO1x1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzEyMFx1ZDBkZFx1YzljMCBcdWFjMWNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQwJm5ic3A7XHVjZDVjXHViMzAwJm5ic3A7MTA8c3VwPjY8XC9zdXA+IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAxIFx1YzcwNFx1Y2U1OCBwXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxJm5ic3A7XHVjOTA0IFx1YjljOFx1YjJlNCZuYnNwO1x1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDEgXHVjNzA0XHVjZTU4IHFcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzJkY1x1Yzc5MVx1YzcwNFx1Y2U1OFx1YWMwMCBwXHVjNzc0XHVhY2UwIFx1YjA1ZFx1YzcwNFx1Y2U1OFx1YWMwMCBxXHVjNzc4IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1Yjc3Y1x1YzZiNFx1YjRkYyBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVkMzI4XHVhYzAwXHViOWRkXHVjMmUwXHVkNTU4XHViMjk0Jm5ic3A7XHVhY2JkXHVjNmIwXHVjNWQ0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDA1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhbWUgU3RyYXRlZ3kiLCJkZXNjcmlwdGlvbiI6IjxwPkFsaWNlIGFuZCBCb2IgYXJlIHBsYXlpbmcgYSBib2FyZCBnYW1lLiBUaGUgYm9hcmQgaXMgZGl2aWRlZCBpbnRvIHBvc2l0aW9ucyBsYWJlbGVkIGEsIGIsIGMsIGQsIC4gLiAuIGFuZCB0aGUgcGxheWVycyB1c2UgYSBnYW1lcGllY2UgdG8gbWFyayB0aGUgY3VycmVudCBwb3NpdGlvbi4gRWFjaCByb3VuZCBvZiB0aGUgZ2FtZSBjb25zaXN0cyBvZiB0d28gc3RlcHM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QWxpY2UgbWFrZXMgYSBjaG9pY2UuIERlcGVuZGluZyBvbiB0aGUgY3VycmVudCBwb3NpdGlvbiwgc2hlIGhhcyBkaWZmZXJlbnQgb3B0aW9ucywgd2hlcmUgZWFjaCBvcHRpb24gaXMgYSBzZXQgb2YgcG9zaXRpb25zLiBBbGljZSBjaG9vc2VzIG9uZSBzZXQgUyBhbW9uZyB0aGUgYXZhaWxhYmxlIHNldHMgb2YgcG9zaXRpb25zLjxcL2xpPlxyXG5cdDxsaT5Cb2IgbWFrZXMgYSBjaG9pY2UuIEhpcyBjaG9pY2UgaXMgb25lIHBvc2l0aW9uIHAgZnJvbSB0aGUgc2V0IFMgdGhhdCBBbGljZSBjaG9zZSBpbiBzdGVwIDEuIEJvYiBtb3ZlcyB0aGUgZ2FtZXBpZWNlIHRvIHBvc2l0aW9uIHAsIHdoaWNoIGlzIHRoZSBwb3NpdGlvbiBmb3IgdGhlIHN0YXJ0IG9mIHRoZSBuZXh0IHJvdW5kLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlByaW9yIHRvIHRoZSBmaXJzdCByb3VuZCwgZWFjaCBwbGF5ZXIgaW5kZXBlbmRlbnRseSBzZWxlY3RzIG9uZSBvZiB0aGUgcG9zaXRpb25zIGFuZCByZXZlYWxzIGl0IGF0IHRoZSBzdGFydCBvZiB0aGUgZ2FtZS4gQm9iJnJzcXVvO3MgcG9zaXRpb24gaXMgd2hlcmUgdGhlIGdhbWUgc3RhcnRzLiBBbGljZSB3aW5zIHRoZSBnYW1lIGlmIHNoZSBjYW4gZm9yY2UgQm9iIHRvIG1vdmUgdGhlIGdhbWVwaWVjZSB0byB0aGUgcG9zaXRpb24gc2hlIGhhcyBjaG9zZW4uIFRvIG1ha2UgdGhpbmdzIGludGVyZXN0aW5nLCB0aGV5IGhhdmUgZGVjaWRlZCB0aGF0IEJvYiB3aWxsIHBheSBBbGljZSBhIGNlcnRhaW4gYW1vdW50IGlmIGhlIGxvc2VzLCBidXQgQWxpY2UgbXVzdCBwYXkgQm9iIGEgY2VydGFpbiBhbW91bnQgYWZ0ZXIgZXZlcnkgcm91bmQuIFRoZSBnYW1lIG5vdyBlbmRzIGlmIEFsaWNlJnJzcXVvO3MgcG9zaXRpb24gaXMgcmVhY2hlZCBvciB3aGVuIEFsaWNlIHJ1bnMgb3V0IG9mIGNhc2guPFwvcD5cclxuXHJcbjxwPkJvdGggQWxpY2UgYW5kIEJvYiBwbGF5IG9wdGltYWxseTogQWxpY2Ugd2lsbCBhbHdheXMgY2hvb3NlIGFuIG9wdGlvbiB0aGF0IHdpbGwgbGVhZCB0byBoZXIgd2lubmluZyB0aGUgZ2FtZSwgaWYgdGhpcyBpcyBwb3NzaWJsZSwgYW5kIEJvYiB3aWxsIGFsd2F5cyB0cnkgdG8gcHJldmVudCBBbGljZSBmcm9tIHdpbm5pbmcuPFwvcD5cclxuXHJcbjxwPkZvciBhbGwgcG9zc2libGUgc3RhcnQgYW5kIGVuZCBwb3NpdGlvbnMsIEFsaWNlIHdvdWxkIGxpa2UgeW91IHRvIGRldGVybWluZSB3aGV0aGVyIHNoZSBjYW4gd2luIHRoZSBnYW1lIGFuZCBpZiBzbywgaG93IG1hbnkgcm91bmRzIGl0IHdpbGwgdGFrZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSB0ZXN0IGNhc2UuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgcG9zaXRpb25zIG4gKDEgJmxlOyBuICZsZTsgMjUpLiBUaGUgbiBwb3NpdGlvbnMgYXJlIGxhYmVsZWQgdXNpbmcgdGhlIGZpcnN0IG4gbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCBpbiBsb3dlcmNhc2UuIFRoZSByZXN0IG9mIHRoZSB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgbiBsaW5lcywgb25lIGZvciBlYWNoIHBvc2l0aW9uIHAsIGluIGFscGhhYmV0aWNhbCBvcmRlci4gVGhlIGxpbmUgZm9yIHBvc2l0aW9uIHAgY29udGFpbnMgdGhlIG9wdGlvbnMgYXZhaWxhYmxlIHRvIEFsaWNlIGluIHBvc2l0aW9uIHAuIEl0IHN0YXJ0cyB3aXRoIHRoZSBudW1iZXIgb2Ygb3B0aW9ucyBtICgxICZsZTsgbSAmbHQ7IDI8c3VwPm48XC9zdXA+KSwgd2hpY2ggaXMgZm9sbG93ZWQgYnkgbSBkaXN0aW5jdCBzdHJpbmdzLCBvbmUgZm9yIGVhY2ggb3B0aW9uLiBFYWNoIHN0cmluZyBjb250YWlucyB0aGUgcG9zaXRpb25zIGF2YWlsYWJsZSB0byBCb2IgaWYgQWxpY2UgY2hvb3NlcyB0aGF0IG9wdGlvbi4gVGhlIHN0cmluZyBoYXMgYXQgbGVhc3QgMSBjaGFyYWN0ZXIsIHRoZSBjaGFyYWN0ZXJzICh3aGljaCBjb3JyZXNwb25kIHRvIHZhbGlkIGJvYXJkIHBvc2l0aW9ucykgYXJlIGluIGFscGhhYmV0aWNhbCBvcmRlciwgYW5kIG5vIGNoYXJhY3RlcnMgYXJlIGR1cGxpY2F0ZWQuIFRoZSB0b3RhbCBudW1iZXIgb2Ygb3B0aW9ucyBmb3IgdGhlIHRlc3QgY2FzZSBpcyBhdCBtb3N0IDEwPHN1cD42PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBwb3NpdGlvbiBwIGluIGFscGhhYmV0aWNhbCBvcmRlciwgZGlzcGxheSBvbmUgbGluZS4gSW4gdGhhdCBsaW5lLCBmb3IgZWFjaCBwb3NpdGlvbiBxIGluIGFscGhhYmV0aWNhbCBvcmRlciBkaXNwbGF5IHRoZSBtaW5pbWFsIG51bWJlciBvZiByb3VuZHMgaW4gd2hpY2ggQWxpY2UgY2FuIGJlIGd1YXJhbnRlZWQgdG8gYXJyaXZlIGF0IHBvc2l0aW9uIHEgd2hlbiBzdGFydGluZyB0aGUgZ2FtZSBpbiBwb3NpdGlvbiBwLCBvciAmbWludXM7MSBpZiBBbGljZSBjYW5ub3QgYmUgZ3VhcmFudGVlZCB0byByZWFjaCBxIGZyb20gcC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > World Finals > ACM-ICPC World Finals 2014 D번

  • 문제를 번역한 사람: ntopia