간선 최소화

베시는 \(1\ldots N\)으로 번호가 붙은 정점 \(N\)개와 간선 \(M\)개를 가진 연결된 무방향 그래프 \(G\)를 가지고 있다 (\(2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}\)). \(G\)에는 자기 루프(정점에서 자기 자신으로 가는 간선)는 있을 수 있지만, 평행 간선(같은 두 끝점을 잇는 여러 간선)은 없다.

\(f_G(a,b)\)를, 각 \(1\le a\le N\)과 \(0\le b\)에 대해 정점 \(1\)에서 정점 \(a\)까지 정확히 \(b\)개의 간선을 지나는 경로가 존재하면 참, 그렇지 않으면 거짓으로 평가되는 불리언 함수라고 하자. 한 간선을 여러 번 지나면 그 횟수만큼 개수에 포함된다.

엘시는 베시를 따라 하고 싶어 한다. 구체적으로, 엘시는 모든 \(a\)와 \(b\)에 대해 \(f_{G'}(a,b)=f_G(a,b)\)가 성립하는 무방향 그래프 \(G'\)를 만들고 싶어 한다.

엘시는 가능한 한 적은 일을 하고 싶으므로, 가능한 가장 작은 그래프를 만들고자 한다. 따라서 여러분의 임무는 \(G'\)가 가질 수 있는 간선 개수의 최솟값을 계산하는 것이다.

각 입력에는 독립적으로 해결해야 하는 \(T\)개(\(1\le T\le 5\cdot 10^4\))의 테스트 케이스가 포함되어 있다. 모든 테스트 케이스에 대한 \(N\)의 합은 \(10^5\)를 넘지 않고, \(M\)의 합은 \(2\cdot 10^5\)를 넘지 않음이 보장된다.

문제 제공: Benjamin Qi

채점 방식

• 입력 3의 모든 테스트 케이스는 \(N\le 5\)를 만족한다.
• 입력 4-5의 모든 테스트 케이스는 \(M=N\)을 만족한다.
• 입력 6-9의 모든 테스트 케이스에서는, 모든 \(b\)에 대해 \(f_G(x,b)=f_G(y,b)\)가 성립하는 경우가 아니라면, \(f_G(x,b)\)는 참이고 \(f_G(y,b)\)는 거짓이 되는 \(b\)가 존재한다.
• 입력 10-15의 모든 테스트 케이스는 \(N\le 10^2\)를 만족한다.
• 입력 16-20의 테스트 케이스는 추가 제약이 없다.

문제 제공: Benjamin Qi

입력의 첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.

각 테스트 케이스의 첫째 줄에 두 정수 \(N\)과 \(M\)이 주어진다.

각 테스트 케이스의 다음 \(M\)개의 줄에는 각각 두 정수 \(x\)와 \(y\) (\(1\le x\le y\le N\))가 주어지는데, 이는 \(G\)에서 \(x\)와 \(y\) 사이에 간선이 존재함을 나타낸다.

가독성을 위해 연속된 테스트 케이스는 빈 줄로 구분된다.

각 테스트 케이스마다 \(G'\)가 가질 수 있는 간선 개수의 최솟값을 한 줄에 하나씩 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > February > Platinum