단방향 링크 네트워크

멀티 컴퓨터 시스템은 여러 개의 노드로 이루어져 있으며, 각 노드는 자신의 메모리를 가진다. 노드들은 단방향 통신 링크로 서로 연결되어 있고, 이 상호 접속 네트워크는 방향 그래프로 나타낼 수 있다. 정점은 노드를, 간선은 단방향 링크를 나타낸다.

상호 접속 네트워크에서 가장 중요한 두 구조는 선형 배열과 링이다.

• 선형 배열: 노드를 순서대로 $0, 1, \dots, k-1$ 로 놓았을 때, 모든 $0 \le i < k-1$ 에 대해 노드 $i$ 에서 노드 $i+1$ 로 향하는 단방향 링크가 존재하는 구조이다. 노드가 1개뿐인 선형 배열도 가능하다.
• 링: 선형 배열에 노드 $k-1$ 에서 노드 $0$ 으로 향하는 단방향 링크를 추가한 구조이다.

병렬 응용을 지원하기 위해, 전체 시스템을 여러 개의 서브 시스템으로 분해하려고 한다. 각 서브 시스템은 링 또는 선형 배열이어야 하며, 서로 노드를 공유할 수 없다.

$k$ 개의 노드로 이루어진 링의 가치는 $k$ 달러이고, $k$ 개의 노드로 이루어진 선형 배열의 가치는 $k-1$ 달러이다. 따라서 노드가 1개인 선형 배열의 가치는 $0$ 달러이다.

상호 접속 네트워크가 주어졌을 때, 시스템을 링과/또는 선형 배열로 분해하여 얻을 수 있는 가치의 최댓값을 구하는 프로그램을 작성하시오.

예를 들어, 어떤 네트워크를 노드 6개로 이루어진 링과 노드 8개로 이루어진 선형 배열로 분해하면 총 가치는 $6 + 7 = 13$ 달러가 되며, 이 값이 가능한 최댓값이 될 수 있다.

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

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