시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB114970056962.118%

문제

멀티 컴퓨터 시스템은 여러 개의 노드로 이루어져 있고, 각 노드는 자체 메모리를 가지고 있다. 시스템 상의 각 노드는 단방향 커뮤니케이션 링크로 서로 연결되어 있다. 시스템의 상호 접속 네트워크는 방향 그래프로 나타낼 수 있다. 정점은 노드를 나타내며, 간선은 네트워크의 단방향 링크를 나타낸다. 그림 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+XHJcblxyXG48cD5cdWQ1NWMgXHViYTQwXHVkMmYwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NTggXHVjMGMxXHVkNjM4IFx1YzgxMVx1YzE4ZCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWI5YzEgXHVhY2ZjXC9cdWI2MTBcdWIyOTQgXHVjMTIwXHVkNjE1IFx1YmMzMFx1YzVmNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjZTU4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViMTc4XHViNGRjXHViOTdjIDFcdWFjMWNcdWI5Y2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzEyMFx1ZDYxNSBcdWJjMzBcdWM1ZjRcdWIzYzQgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHVjZTU4XHViMjk0IDAgXHViMmVjXHViN2VjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ludGVyY29ubi5wbmdcIiBzdHlsZT1cImhlaWdodDozMDVweDsgd2lkdGg6MzY1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWFkZjhcdWI5YmMgMTxcL3N0cm9uZz4uIFx1YzBjMVx1ZDYzOCBcdWM1ZjBcdWFjYjAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViOTdjIFx1YjE3OFx1YjRkYyA2XHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI5YzEgKFx1YmU2OFx1YWMwNFx1YzBjOSlcdWFjZmMgXHViMTc4XHViNGRjIDhcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzEyMFx1ZDYxNSBcdWJjMzBcdWM1ZjQgKFx1Y2QwOFx1Yjg1ZFx1YzBjOSkgXHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU3NFx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJkODRcdWQ1NzRcdWM3NTggXHVjZDFkIFx1YWMwMFx1Y2U1OFx1YjI5NCAxM1x1YjJlY1x1YjdlY1x1Yzc3NFx1YWNlMCwgXHVjNzc0IFx1YWMxMlx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzI5XHViYzk1XHVjOTExIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVkNjM4IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1YjJlOFx1YmMyOVx1ZDVhNSBcdWI5YzFcdWQwNmNcdWM3NTggXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAobiAmbGU7IDEsMDAwLCBtICZsZTsgNTAsMDAwKSBcdWIxNzhcdWI0ZGNcdWIyOTQgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBuLTFcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCB1XHVjNWQwXHVjMTFjIHZcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YjJlOFx1YmMyOVx1ZDVhNSBcdWI5YzFcdWQwNmNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggdVx1YzY0MCB2XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVkNTZkXHVjMGMxIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVkNTVjIFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWQzZWNcdWQ1NjhcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMwYzFcdWQ2MzggXHVjODExXHVjMThkIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjk3YyBcdWI5YzEgXHVhY2ZjXC9cdWI2MTBcdWIyOTQgXHVjMTIwXHVkNjE1IFx1YmMzMFx1YzVmNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzI5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5ldHdvcmtzIHdpdGggVW5pZGlyZWN0aW9uYWwgTGlua3MiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgbXVsdGljb21wdXRlciBzeXN0ZW0gdGhhdCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBub2RlcywgZWFjaCB3aXRoIGl0cyBvd24gbWVtb3J5LiBUaGUgbm9kZXMgaW4gdGhlIHN5c3RlbSBhcmUgaW50ZXJjb25uZWN0ZWQgdmlhIHVuaWRpcmVjdGlvbmFsIGNvbW11bmljYXRpb24gbGlua3MuIFRoZSBpbnRlcmNvbm5lY3Rpb24gbmV0d29yayBvZiB0aGUgc3lzdGVtLCByZXByZXNlbnRpbmcgdGhlIHdheSBpbiB3aGljaCB0aGUgbm9kZXMgYXJlIGNvbm5lY3RlZCB0b2dldGhlciwgaXMgbW9kZWxlZCBhcyBhIGRpcmVjdGVkIGdyYXBoLCB3aGVyZSB2ZXJ0aWNlcyBhbmQgZGlyZWN0ZWQgZWRnZXMgcmVzcGVjdGl2ZWx5IHJlcHJlc2VudCBub2RlcyBhbmQgdW5pZGlyZWN0aW9uYWwgbGlua3Mgb2YgdGhlIG5ldHdvcmsuIEZpZ3VyZSAxIHNob3dzIGFuIGV4YW1wbGUgb2YgaW50ZXJjb25uZWN0aW9uIG5ldHdvcmtzIHdpdGggZm91cnRlZW4gbm9kZXMgaW50ZXJjb25uZWN0ZWQgdmlhIG5pbmV0ZWVuIHVuaWRpcmVjdGlvbmFsIGxpbmtzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MaW5lYXIgYXJyYXlzIGFuZCByaW5ncyBhcmUgdHdvIG9mIHRoZSBpbXBvcnRhbnQgY29tcHV0YXRpb25hbCBzdHJ1Y3R1cmVzIGluIGludGVyY29ubmVjdGlvbiBuZXR3b3Jrcy4gSW4gYSBsaW5lYXIgYXJyYXksIGVhY2ggbm9kZSBleGNlcHQgZm9yIHRoZSBleHRyZW1lIGVuZHMgaGFzIHR3byBuZWlnaGJvcmluZyBub2Rlcywgb25lIHRvIGl0cyBsZWZ0IGFuZCBvbmUgdG8gaXRzIHJpZ2h0LCB3aGVyZSB0aGUgdHdvIG5vZGVzIGF0IHRoZSBlbmRzIGFyZSBjb25uZWN0ZWQgdG8gdGhlaXIgc2luZ2xlIG5laWdoYm9yLiBJZiB0aGUgbm9kZXMgYXQgZWl0aGVyIGVuZCBhcmUgY29ubmVjdGVkLCB3ZSByZWZlciB0byBpdCBhcyBhIHJpbmcuIE1vcmUgc3BlY2lmaWNhbGx5LCB0aGUgbm9kZXMgb2YgYSBsaW5lYXIgYXJyYXkgd2l0aCBrIG5vZGVzIGNhbiBiZSBudW1iZXJlZCBmcm9tIDAgdG8gay0xIHNvIHRoYXQgdGhlcmUgZXhpc3RzIGEgdW5pZGlyZWN0aW9uYWwgbGluayBmcm9tIG5vZGUgaSB0byBub2RlIGkrMSBmb3IgZXZlcnkgMCAmbGU7IGkgJmx0OyBrLTEuIFRoZSBsaW5lYXIgYXJyYXkgYmVjb21lcyBhIHJpbmcgaWYgd2UgYWRkIGEgdW5pZGlyZWN0aW9uYWwgbGluayBmcm9tIHRoZSBub2RlIGstMSB0byB0aGUgbm9kZSAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UbyBzdXBwb3J0IHBhcmFsbGVsIGFwcGxpY2F0aW9ucyB0aGF0IHJlcXVpcmUgb25lIG9mIHRoZSB0d28gYWZvcmVtZW50aW9uZWQgY29tcHV0YXRpb25hbCBzdHJ1Y3R1cmVzLCB3ZSBuZWVkcyB0byBkZWNvbXBvc2UgdGhlIHN5c3RlbSBpbnRvIHNldmVyYWwgc3Vic3lzdGVtcyBlYWNoIG9mIHdob3NlIGludGVyY29ubmVjdGlvbiBuZXR3b3JrcyBpcyBhIHJpbmcgb3IgYSBsaW5lYXIgYXJyYXkuIFRoZSBzdWJzeXN0ZW1zIHNob3VsZCBiZSBwYWlyd2lzZSBub2RlLWRpc2pvaW50LCBpLmUuLCBubyB0d28gc3Vic3lzdGVtcyBzaGFyZSBhIGNvbW1vbiBub2RlLiBBY2NvcmRpbmcgdG8gYSByZWNlbnQgcmVwb3J0LCBhIHJpbmcgY29tcG9zZWQgb2YgayBub2RlcyBpcyB3b3J0aCBrIGRvbGxhcnMgd2hpbGUgYSBsaW5lYXIgYXJyYXkgb2YgayBub2RlcyBpcyB3b3J0aCBrLTEgZG9sbGFycy4gVGhpcyBtb3RpdmF0ZXMgdGhlIHN0dWR5IG9uIGhvdyB0byBkZWNvbXBvc2UgdGhlIHN5c3RlbSBpbnRvIHN1YnN5c3RlbXMgaW4gb3JkZXIgdG8gbWF4aW1pemUgcHJvZml0cy4gWW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gZm9yIGRlY29tcG9zaW5nIHRoZSBpbnRlcmNvbm5lY3Rpb24gbmV0d29yayBvZiBvdXIgbXVsdGljb21wdXRlciBzeXN0ZW0gaW50byByaW5ncyBhbmRcL29yIGxpbmVhciBhcnJheXMgd2hvc2UgdG90YWwgdmFsdWUgaXMgdGhlIG1heGltdW0gcG9zc2libGUuIE5vdGUgdGhhdCBhIGxpbmVhciBhcnJheSBtYXkgaGF2ZSBvbmx5IG9uZSBub2RlIGFuZCBpbiB0aGF0IGNhc2UsIGl0cyB2YWx1ZSBpcyB6ZXJvIGRvbGxhci48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9pbnRlcmNvbm4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzA1cHg7IHdpZHRoOjM2NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+RmlndXJlIDE8XC9zdHJvbmc+LiBBbiBpbnRlcmNvbm5lY3Rpb24gbmV0d29yayBhbmQgaXRzIGRlY29tcG9zaXRpb24gaW50byBhIHJpbmcgb2Ygc2l4IG5vZGVzIChyZWQpIGFuZCBhIGxpbmVhciBhcnJheSBvZiBlaWdodCBub2RlcyAoZ3JlZW4pLiBUaGUgdG90YWwgdmFsdWUgb2YgdGhpcyBkZWNvbXBvc2l0aW9uIGlzIHRoaXJ0ZWVuIGRvbGxhcnMsIHdoaWNoIGlzIHRoZSBtYXhpbXVtIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcywgd2hlcmUgdGhlIHBvc2l0aXZlIGludGVnZXIgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQsIGZvbGxvd2VkIGJ5IHRoZSBkZXNjcmlwdGlvbiBvZiBlYWNoIHRlc3QgY2FzZS4gVGhlIGZpcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIG0sIHJlc3BlY3RpdmVseSBpbmRpY2F0aW5nIHRoZSBudW1iZXJzIG9mIG5vZGVzIGFuZCB1bmlkaXJlY3Rpb25hbCBsaW5rcyBpbiBhbiBpbnRlcmNvbm5lY3Rpb24gbmV0d29yaywgaW4gd2hpY2ggd2UgYXNzdW1lIG4gJmxlOyAxLDAwMCBhbmQgbSAmbGU7IDUwLDAwMC4gVGhlIG5vZGVzIGFyZSBpbmRleGVkIDAgdG8gbi0xLiBJbiB0aGUgZm9sbG93aW5nIG0gbGluZXMsIGVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgdSBhbmQgdiwgd2hpY2ggcmVwcmVzZW50IGEgdW5pZGlyZWN0aW9uYWwgbGluayBmcm9tIG5vZGUgdSB0byBub2RlIHYuIFRoZSB0d28gaW50ZWdlcnMgZ2l2ZW4gaW4gYSBzaW5nbGUgbGluZSBhcmUgYWx3YXlzIHNlcGFyYXRlZCBieSBhIHNwYWNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyLCByZXByZXNlbnRpbmcgdGhlIG1heGltdW0gdG90YWwgdmFsdWUgaW4gZG9sbGFycyB0aGF0IGNhbiBiZSBhY2hpZXZlZCBieSBkZWNvbXBvc2luZyB0aGUgaW50ZXJjb25uZWN0aW9uIG5ldHdvcmsgaW50byByaW5ncyBhbmRcL29yIGxpbmVhciBhcnJheXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 H번

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