시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 282 114 88 42.308%

문제

멀티 컴퓨터 시스템은 여러 개의 노드로 이루어져 있고, 각 노드는 자체 메모리를 가지고 있다. 시스템 상의 각 노드는 단방향 커뮤니케이션 링크로 서로 연결되어 있다. 시스템의 상호 접속 네트워크는 방향 그래프로 나타낼 수 있다. 정점은 노드를 나타내며, 간선은 네트워크의 단방향 링크를 나타낸다. 그림 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가 주어진다. 두 정수는 한 줄에 주어지며, 항상 공백으로 구분되어져 있다.

출력

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

예제 입력

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

예제 출력

3
5
13

힌트

출처

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

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