페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5776
서브태스크

Minimizing Edges 1s 512MB

문제

베시는 정점이 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를 넘지 않는다.


입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.

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

다음 M개의 줄에는 두 정수 x, y(1≤x≤y≤N)가 주어지며, 이는 G에 정점 x와 정점 y를 잇는 간선이 존재함을 의미한다.

가독성을 위해, 연속한 테스트 케이스 사이에는 빈 줄이 포함될 수 있다.


출력

각 테스트 케이스마다 조건을 만족하는 G′의 최소 간선 개수를 한 줄에 하나씩 출력하라.


부분문제

번호 점수 조건
#110점

N≤5

#210점
M=N
#320점

모든 b에 대해 f_G(x,b)=f_G(y,b)가 성립하지 않는 두 정점 x,y가 존재한다면, 어떤 b가 존재하여 f_G(x,b)는 참이고 f_G(y,b)는 거짓이다.

#430점
N≤10^2
#530점
추가 제약 조건이 없다.

예제 #1

2

5 5
1 2
2 3
2 5
1 4
4 5

5 5
1 2
2 3
3 4
4 5
1 5
4
5

첫 번째 테스트 케이스에서 엘시는 G에서 간선 (2,5)를 제거하여 G′를 만들 수 있다. 또는 G에서 간선을 제거하는 것만 허용되는 것이 아니므로, 다음과 같은 간선들로 이루어진 그래프를 만들어도 된다:

1 2
1 4
4 3
4 5

G′ 역시 연결 그래프여야 하므로, 엘시는 N−1보다 더 적은 간선으로는 절대로 만들 수 없다.


예제 #2

7

8 10
1 2
1 3
1 4
1 5
2 6
3 7
4 8
5 8
6 7
8 8

10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9

13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13

16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16

21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21

20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20

24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 24
10
11
15
18
22
26
31

각 테스트 케이스에서 엘시는 베시보다 더 적은 간선으로는 절대로 만들 수 없다.


출처

USACO 2021 Febuary Platinum
로그인해야 코드를 작성할 수 있어요.