베시는 정점이 N개이고 1…N으로 번호가 매겨진 연결된 무방향 그래프 G를 가지고 있다. 간선은 M개이며 (2≤N≤10^5, N−1≤M≤(N^2+N)/2)이다. G에는 자기 자신으로 향하는 간선(셀프 루프)이 있을 수 있지만, 같은 두 정점을 잇는 중복 간선(평행 간선)은 존재하지 않는다.

f_G(a,b)를 다음과 같은 불리언 함수라고 하자. 모든 1≤a≤N 및 0≤b에 대해, 정점 1에서 정점 a까지 가는 경로 중에서 정확히 b개의 간선을 지나가는 경로가 존재하면 참, 그렇지 않으면 거짓이다. 한 간선을 여러 번 지나갈 수 있으며, 그 경우 지나간 횟수만큼 간선 수에 포함된다.

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

엘시는 가능한 한 적게 일하고 싶으므로, 가능한 한 작은 그래프를 만들고자 한다. 따라서 여러분의 목표는 조건을 만족하는 G′ 중에서 간선의 개수가 최소가 되도록 할 때, 그 최소 간선 개수를 구하는 것이다.

입력에는 T(1≤T≤5⋅10^4)개의 테스트 케이스가 있으며, 각 테스트 케이스는 서로 독립적으로 해결해야 한다. 모든 테스트 케이스에 대해 N의 합은 10^5를 넘지 않고, M의 합은 2⋅10^5를 넘지 않는다.

#5776 upload 43 done 1 how_to_reg 1 call_split サブタスク

Minimizing Edges timer 1s memory 512MB

#5776
サブタスク

Minimizing Edges 1s 512MB