시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 395 186 143 49.141%

문제

멀티 컴퓨터 시스템은 여러 개의 노드로 이루어져 있고, 각 노드는 자체 메모리를 가지고 있다. 시스템 상의 각 노드는 단방향 커뮤니케이션 링크로 서로 연결되어 있다. 시스템의 상호 접속 네트워크는 방향 그래프로 나타낼 수 있다. 정점은 노드를 나타내며, 간선은 네트워크의 단방향 링크를 나타낸다. 그림 1은 14개의 노드가 19개의 단방향 링크로 서로 연결된 상호 접속 네트워크를 나타낸다.

선형 배열과 링은 상호 접속 네트워크에서 가장 중요한 두 구조이다. 선형 배열에서 각 양 끝 노드를 제외한 모든 노드는 인접한 노드를 두 개 가진다. 한 노드는 왼쪽, 다른 노드는 오른쪽에 있으며, 두 노드는 모두 공통된 이웃을 통해 연결되어 있다. 이 구조에서 양 끝 점이 연결되었을 때, 그 구조를 링이라고 한다. 즉, 0번부터 k-1번까지, k개 노드로 이루어진 선형 배열은 모든 0 ≤ i < k-1에 대해서 노드 i에서 노드 i+1로 단방향 링크가 존재해야 한다. 여기서 노드 k-1과 노드 0을 연결하는 단방향 링크를 추가하면 링이 된다.

병렬 어플리케이션을 지원하려면, 앞에서 설명한 두 구조 중 하나가 필요하다. 따라서, 시스템을 여러 개의 서브 시스템으로 분해해야 한다. 각 서브 시스템은 링 또는 선형 배열이어야 한다. 서브 시스템은 공통된 노드를 공유할 수 없다.

최근에 발표된 한 보고서에 의하면, k개 노드로 이루어진 링의 가치는 k 달러이고, k개의 노드로 이루어진 선형 배열의 가치는 k-1 달러이다. 따라서, 이익을 최대로 하면서, 시스템을 서브 시스템으로 분해하는 연구가 진행중이다. 

한 멀티 컴퓨터 시스템의 상호 접속 네트워크가 주어졌을 때, 이 시스템을 링 과/또는 선형 배열로 분해해서 가치를 최대로 하는 프로그램을 작성하시오. 노드를 1개만 가지는 선형 배열도 존재할 수 있다. 이 때, 가치는 0 달러이다.

그림 1. 상호 연결 네트워크를 노드 6개로 이루어진 링 (빨간색)과 노드 8개로 이루어진 선형 배열 (초록색) 으로 분해한 그림이다. 이 분해의 총 가치는 13달러이고, 이 값은 가능한 방법중 최대값이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상호 네트워크를 이루는 노드의 수 n과 단방향 링크의 수 m이 주어진다. (n ≤ 1,000, m ≤ 50,000) 노드는 0번부터 n-1번까지 번호가 매겨져 있다. 다음 m개 줄에는 u에서 v로 향하는 단방향 링크를 나타내는 두 정수 u와 v가 주어진다. 두 정수는 한 줄에 주어지며, 항상 공백으로 구분되어져 있다.

출력

각 테스트 케이스 마다, 한 줄을 출력한다. 이 줄에는 정수를 하나 포함해야 하며, 정수는 입력으로 주어진 상호 접속 네트워크를 링 과/또는 선형 배열로 분해했을 때 얻을 수 있는 가치의 최대값이다.

예제 입력 1

3
4 3
3 2
1 0
2 3
6 6
0 1
1 2
2 3
3 1
3 4
4 5
14 19
0 1
1 2
2 3
3 4
4 5
5 0
5 4
2 1
2 6
6 7
7 8
8 9
9 1
8 7
7 10
10 11
11 12
12 13
13 8

예제 출력 1

3
5
13
W3sicHJvYmxlbV9pZCI6IjMyOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWJjMjlcdWQ1YTUgXHViOWMxXHVkMDZjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyIsImRlc2NyaXB0aW9uIjoiPHA+XHViYTQwXHVkMmYwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWM3OTBcdWNjYjQgXHViYTU0XHViYWE4XHViOWFjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzJkY1x1YzJhNFx1ZDE1YyBcdWMwYzFcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWIyZThcdWJjMjlcdWQ1YTUgXHVjZWU0XHViYmE0XHViMmM4XHVjZjAwXHVjNzc0XHVjMTU4IFx1YjljMVx1ZDA2Y1x1Yjg1YyBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzU4IFx1YzBjMVx1ZDYzOCBcdWM4MTFcdWMxOGQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViMjk0IFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWFjMDRcdWMxMjBcdWM3NDAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNzU4IFx1YjJlOFx1YmMyOVx1ZDVhNSBcdWI5YzFcdWQwNmNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFkZjhcdWI5YmMgMVx1Yzc0MCAxNFx1YWMxY1x1Yzc1OCBcdWIxNzhcdWI0ZGNcdWFjMDAgMTlcdWFjMWNcdWM3NTggXHViMmU4XHViYzI5XHVkNWE1IFx1YjljMVx1ZDA2Y1x1Yjg1YyBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzBjMVx1ZDYzOCBcdWM4MTFcdWMxOGQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVkNjE1IFx1YmMzMFx1YzVmNFx1YWNmYyBcdWI5YzFcdWM3NDAgXHVjMGMxXHVkNjM4IFx1YzgxMVx1YzE4ZCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWI0NTAgXHVhZDZjXHVjODcwXHVjNzc0XHViMmU0LiBcdWMxMjBcdWQ2MTUgXHViYzMwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YWMwMSBcdWM1OTEgXHViMDVkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTc4XHViNGRjXHViOTdjIFx1YjQ1MCBcdWFjMWMgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWQ1NWMgXHViMTc4XHViNGRjXHViMjk0IFx1YzY3Y1x1Y2FiZCwgXHViMmU0XHViOTc4IFx1YjE3OFx1YjRkY1x1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHViMTc4XHViNGRjXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjZjVcdWQxYjVcdWI0MWMgXHVjNzc0XHVjNmMzXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhZDZjXHVjODcwXHVjNWQwXHVjMTFjJm5ic3A7XHVjNTkxIFx1YjA1ZCBcdWM4MTBcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YWQ2Y1x1Yzg3MFx1Yjk3YyBcdWI5YzFcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIDBcdWJjODhcdWJkODBcdWQxMzAgay0xXHViYzg4XHVhZTRjXHVjOWMwLCBrXHVhYzFjIFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMTIwXHVkNjE1IFx1YmMzMFx1YzVmNFx1Yzc0MCBcdWJhYThcdWI0ZTAgMCAmbGU7IGkgJmx0OyBrLTFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjE3OFx1YjRkYyBpXHVjNWQwXHVjMTFjIFx1YjE3OFx1YjRkYyBpKzFcdWI4NWMgXHViMmU4XHViYzI5XHVkNWE1IFx1YjljMVx1ZDA2Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgXHViMTc4XHViNGRjIGstMVx1YWNmYyBcdWIxNzhcdWI0ZGMgMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViMmU4XHViYzI5XHVkNWE1IFx1YjljMVx1ZDA2Y1x1Yjk3YyBcdWNkOTRcdWFjMDBcdWQ1NThcdWJhNzQgXHViOWMxXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2QxXHViODJjJm5ic3A7XHVjNWI0XHVkNTBjXHViOWFjXHVjZjAwXHVjNzc0XHVjMTU4XHVjNzQ0IFx1YzljMFx1YzZkMFx1ZDU1OFx1YjgyNFx1YmE3NCwgXHVjNTVlXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWI0NTAgXHVhZDZjXHVjODcwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YzExY1x1YmUwYyBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTc0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzExY1x1YmUwYyBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDAgXHViOWMxIFx1YjYxMFx1YjI5NCBcdWMxMjBcdWQ2MTUgXHViYzMwXHVjNWY0XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMTFjXHViZTBjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0MCBcdWFjZjVcdWQxYjVcdWI0MWMgXHViMTc4XHViNGRjXHViOTdjIFx1YWNmNVx1YzcyMFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmNcdWM1ZDAgXHViYzFjXHVkNDVjXHViNDFjIFx1ZDU1YyBcdWJjZjRcdWFjZTBcdWMxMWNcdWM1ZDAgXHVjNzU4XHVkNTU4XHViYTc0LCBrXHVhYzFjIFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViOWMxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YjI5NCBrIFx1YjJlY1x1YjdlY1x1Yzc3NFx1YWNlMCwga1x1YWMxY1x1Yzc1OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzEyMFx1ZDYxNSBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzAwXHVjZTU4XHViMjk0IGstMSBcdWIyZWNcdWI3ZWNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNzc0XHVjNzc1XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWJhNzRcdWMxMWMsIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWMxMWNcdWJlMGMgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU3NFx1ZDU1OFx1YjI5NCBcdWM1ZjBcdWFkNmNcdWFjMDAgXHVjOWM0XHVkNTg5XHVjOTExXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHViYTQwXHVkMmYwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NTggXHVjMGMxXHVkNjM4IFx1YzgxMVx1YzE4ZCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWI5YzEgXHVhY2ZjXC9cdWI2MTBcdWIyOTQgXHVjMTIwXHVkNjE1IFx1YmMzMFx1YzVmNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjZTU4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViMTc4XHViNGRjXHViOTdjIDFcdWFjMWNcdWI5Y2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzEyMFx1ZDYxNSBcdWJjMzBcdWM1ZjRcdWIzYzQgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMFx1Y2U1OFx1YjI5NCAwIFx1YjJlY1x1YjdlY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9pbnRlcmNvbm4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzA1cHg7IHdpZHRoOjM2NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViOWJjIDE8XC9zdHJvbmc+LiBcdWMwYzFcdWQ2MzggXHVjNWYwXHVhY2IwIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjk3YyBcdWIxNzhcdWI0ZGMgNlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViOWMxIChcdWJlNjhcdWFjMDRcdWMwYzkpXHVhY2ZjIFx1YjE3OFx1YjRkYyA4XHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMxMjBcdWQ2MTUgXHViYzMwXHVjNWY0IChcdWNkMDhcdWI4NWRcdWMwYzkpIFx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NWMgXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViZDg0XHVkNTc0XHVjNzU4IFx1Y2QxZCBcdWFjMDBcdWNlNThcdWIyOTQgMTNcdWIyZWNcdWI3ZWNcdWM3NzRcdWFjZTAsIFx1Yzc3NCBcdWFjMTJcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1YzkxMSBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1ZDYzOCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWMyMTggblx1YWNmYyBcdWIyZThcdWJjMjlcdWQ1YTUgXHViOWMxXHVkMDZjXHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKG4gJmxlOyAxLDAwMCwgbSAmbGU7IDUwLDAwMCkgXHViMTc4XHViNGRjXHViMjk0IDBcdWJjODhcdWJkODBcdWQxMzAgbi0xXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgdVx1YzVkMFx1YzExYyB2XHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWIyZThcdWJjMjlcdWQ1YTUgXHViOWMxXHVkMDZjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IHVcdWM2NDAgdlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWMyMThcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDU2ZFx1YzBjMSBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVkM2VjXHVkNTY4XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjODE1XHVjMjE4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGMxXHVkNjM4IFx1YzgxMVx1YzE4ZCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHViOWMxIFx1YWNmY1wvXHViNjEwXHViMjk0IFx1YzEyMFx1ZDYxNSBcdWJjMzBcdWM1ZjRcdWI4NWMgXHViZDg0XHVkNTc0XHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWNlNThcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMyOTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZXR3b3JrcyB3aXRoIFVuaWRpcmVjdGlvbmFsIExpbmtzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIG11bHRpY29tcHV0ZXIgc3lzdGVtIHRoYXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2Ygbm9kZXMsIGVhY2ggd2l0aCBpdHMgb3duIG1lbW9yeS4gVGhlIG5vZGVzIGluIHRoZSBzeXN0ZW0gYXJlIGludGVyY29ubmVjdGVkIHZpYSB1bmlkaXJlY3Rpb25hbCBjb21tdW5pY2F0aW9uIGxpbmtzLiBUaGUgaW50ZXJjb25uZWN0aW9uIG5ldHdvcmsgb2YgdGhlIHN5c3RlbSwgcmVwcmVzZW50aW5nIHRoZSB3YXkgaW4gd2hpY2ggdGhlIG5vZGVzIGFyZSBjb25uZWN0ZWQgdG9nZXRoZXIsIGlzIG1vZGVsZWQgYXMgYSBkaXJlY3RlZCBncmFwaCwgd2hlcmUgdmVydGljZXMgYW5kIGRpcmVjdGVkIGVkZ2VzIHJlc3BlY3RpdmVseSByZXByZXNlbnQgbm9kZXMgYW5kIHVuaWRpcmVjdGlvbmFsIGxpbmtzIG9mIHRoZSBuZXR3b3JrLiBGaWd1cmUgMSBzaG93cyBhbiBleGFtcGxlIG9mIGludGVyY29ubmVjdGlvbiBuZXR3b3JrcyB3aXRoIGZvdXJ0ZWVuIG5vZGVzIGludGVyY29ubmVjdGVkIHZpYSBuaW5ldGVlbiB1bmlkaXJlY3Rpb25hbCBsaW5rcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGluZWFyIGFycmF5cyBhbmQgcmluZ3MgYXJlIHR3byBvZiB0aGUgaW1wb3J0YW50IGNvbXB1dGF0aW9uYWwgc3RydWN0dXJlcyBpbiBpbnRlcmNvbm5lY3Rpb24gbmV0d29ya3MuIEluIGEgbGluZWFyIGFycmF5LCBlYWNoIG5vZGUgZXhjZXB0IGZvciB0aGUgZXh0cmVtZSBlbmRzIGhhcyB0d28gbmVpZ2hib3Jpbmcgbm9kZXMsIG9uZSB0byBpdHMgbGVmdCBhbmQgb25lIHRvIGl0cyByaWdodCwgd2hlcmUgdGhlIHR3byBub2RlcyBhdCB0aGUgZW5kcyBhcmUgY29ubmVjdGVkIHRvIHRoZWlyIHNpbmdsZSBuZWlnaGJvci4gSWYgdGhlIG5vZGVzIGF0IGVpdGhlciBlbmQgYXJlIGNvbm5lY3RlZCwgd2UgcmVmZXIgdG8gaXQgYXMgYSByaW5nLiBNb3JlIHNwZWNpZmljYWxseSwgdGhlIG5vZGVzIG9mIGEgbGluZWFyIGFycmF5IHdpdGggayBub2RlcyBjYW4gYmUgbnVtYmVyZWQgZnJvbSAwIHRvIGstMSBzbyB0aGF0IHRoZXJlIGV4aXN0cyBhIHVuaWRpcmVjdGlvbmFsIGxpbmsgZnJvbSBub2RlIGkgdG8gbm9kZSBpKzEgZm9yIGV2ZXJ5IDAgJmxlOyBpICZsdDsgay0xLiBUaGUgbGluZWFyIGFycmF5IGJlY29tZXMgYSByaW5nIGlmIHdlIGFkZCBhIHVuaWRpcmVjdGlvbmFsIGxpbmsgZnJvbSB0aGUgbm9kZSBrLTEgdG8gdGhlIG5vZGUgMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gc3VwcG9ydCBwYXJhbGxlbCBhcHBsaWNhdGlvbnMgdGhhdCByZXF1aXJlIG9uZSBvZiB0aGUgdHdvIGFmb3JlbWVudGlvbmVkIGNvbXB1dGF0aW9uYWwgc3RydWN0dXJlcywgd2UgbmVlZHMgdG8gZGVjb21wb3NlIHRoZSBzeXN0ZW0gaW50byBzZXZlcmFsIHN1YnN5c3RlbXMgZWFjaCBvZiB3aG9zZSBpbnRlcmNvbm5lY3Rpb24gbmV0d29ya3MgaXMgYSByaW5nIG9yIGEgbGluZWFyIGFycmF5LiBUaGUgc3Vic3lzdGVtcyBzaG91bGQgYmUgcGFpcndpc2Ugbm9kZS1kaXNqb2ludCwgaS5lLiwgbm8gdHdvIHN1YnN5c3RlbXMgc2hhcmUgYSBjb21tb24gbm9kZS4gQWNjb3JkaW5nIHRvIGEgcmVjZW50IHJlcG9ydCwgYSByaW5nIGNvbXBvc2VkIG9mIGsgbm9kZXMgaXMgd29ydGggayBkb2xsYXJzIHdoaWxlIGEgbGluZWFyIGFycmF5IG9mIGsgbm9kZXMgaXMgd29ydGggay0xIGRvbGxhcnMuIFRoaXMgbW90aXZhdGVzIHRoZSBzdHVkeSBvbiBob3cgdG8gZGVjb21wb3NlIHRoZSBzeXN0ZW0gaW50byBzdWJzeXN0ZW1zIGluIG9yZGVyIHRvIG1heGltaXplIHByb2ZpdHMuIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIGZvciBkZWNvbXBvc2luZyB0aGUgaW50ZXJjb25uZWN0aW9uIG5ldHdvcmsgb2Ygb3VyIG11bHRpY29tcHV0ZXIgc3lzdGVtIGludG8gcmluZ3MgYW5kXC9vciBsaW5lYXIgYXJyYXlzIHdob3NlIHRvdGFsIHZhbHVlIGlzIHRoZSBtYXhpbXVtIHBvc3NpYmxlLiBOb3RlIHRoYXQgYSBsaW5lYXIgYXJyYXkgbWF5IGhhdmUgb25seSBvbmUgbm9kZSBhbmQgaW4gdGhhdCBjYXNlLCBpdHMgdmFsdWUgaXMgemVybyBkb2xsYXIuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaW50ZXJjb25uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMwNXB4OyB3aWR0aDozNjVweFwiIFwvPjxcL3A+XHJcblxyXG48cD48c3Ryb25nPkZpZ3VyZSAxPFwvc3Ryb25nPi4gQW4gaW50ZXJjb25uZWN0aW9uIG5ldHdvcmsgYW5kIGl0cyBkZWNvbXBvc2l0aW9uIGludG8gYSByaW5nIG9mIHNpeCBub2RlcyAocmVkKSBhbmQgYSBsaW5lYXIgYXJyYXkgb2YgZWlnaHQgbm9kZXMgKGdyZWVuKS4gVGhlIHRvdGFsIHZhbHVlIG9mIHRoaXMgZGVjb21wb3NpdGlvbiBpcyB0aGlydGVlbiBkb2xsYXJzLCB3aGljaCBpcyB0aGUgbWF4aW11bSBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMsIHdoZXJlIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LCBmb2xsb3dlZCBieSB0aGUgZGVzY3JpcHRpb24gb2YgZWFjaCB0ZXN0IGNhc2UuIFRoZSBmaXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBuIGFuZCBtLCByZXNwZWN0aXZlbHkgaW5kaWNhdGluZyB0aGUgbnVtYmVycyBvZiBub2RlcyBhbmQgdW5pZGlyZWN0aW9uYWwgbGlua3MgaW4gYW4gaW50ZXJjb25uZWN0aW9uIG5ldHdvcmssIGluIHdoaWNoIHdlIGFzc3VtZSBuICZsZTsgMSwwMDAgYW5kIG0gJmxlOyA1MCwwMDAuIFRoZSBub2RlcyBhcmUgaW5kZXhlZCAwIHRvIG4tMS4gSW4gdGhlIGZvbGxvd2luZyBtIGxpbmVzLCBlYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIHUgYW5kIHYsIHdoaWNoIHJlcHJlc2VudCBhIHVuaWRpcmVjdGlvbmFsIGxpbmsgZnJvbSBub2RlIHUgdG8gbm9kZSB2LiBUaGUgdHdvIGludGVnZXJzIGdpdmVuIGluIGEgc2luZ2xlIGxpbmUgYXJlIGFsd2F5cyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciwgcmVwcmVzZW50aW5nIHRoZSBtYXhpbXVtIHRvdGFsIHZhbHVlIGluIGRvbGxhcnMgdGhhdCBjYW4gYmUgYWNoaWV2ZWQgYnkgZGVjb21wb3NpbmcgdGhlIGludGVyY29ubmVjdGlvbiBuZXR3b3JrIGludG8gcmluZ3MgYW5kXC9vciBsaW5lYXIgYXJyYXlzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2013 H번

  • 문제의 오타를 찾은 사람: arine kipa00
  • 문제를 번역한 사람: baekjoon
  • 데이터를 만든 사람: myungwoo
  • 잘못된 데이터를 찾은 사람: Nada