만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

전장의 도로 놓기

시간 제한5초메모리 제한512 MB

요약
각 테스트 케이스마다 모든 도로를 정확히 한 번씩 지나 출발 도시로 돌아오는 경로가 가능하도록 추가할 도로 수의 최솟값을 구합니다.
난이도

보통10점 중 6점

유형
그래프, 유니온 파인드, 수학
정답자
아직 제출이 없습니다

문제

전장은 도시 NN개와 양방향 도로 RR개로 이루어져 있다. 원하는 도시 CC 하나를 골라 출발해서 RR개의 도로를 각각 정확히 한 번씩 지난 뒤 다시 CC로 돌아오는 것이 목표다.

그런 이동이 불가능하면 도로를 새로 놓아 가능하게 만들어야 하고, 새로 놓는 도로의 개수는 최소여야 한다. 같은 두 도시를 잇는 도로가 여러 개 있을 수 있다. 새 도로는 서로 다른 두 도시 사이라면 어디든 놓을 수 있고, 이미 도로가 있는 두 도시 사이에도 다시 놓을 수 있다.

각 테스트 케이스마다 새로 놓아야 하는 도로의 최소 개수를 구한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어지고, 각 테스트 케이스는 다음과 같다.

  • 한 줄에 도시의 수 NN
  • 한 줄에 도로의 수 RR
  • 도로를 나타내는 RR개의 줄. 각 줄에는 그 도로의 두 끝 도시 AA와 BB가 공백 하나로 구분되어 주어진다. AA와 BB는 서로 다른 정수이고 0≤A,B<N0 \le A, B < N이다.

제한

  • 1≤T≤301 \le T \le 30
  • 2≤N≤10002 \le N \le 1000
  • 1≤R≤1041 \le R \le 10^4

출력

각 테스트 케이스마다 한 줄에 Case #x: 를 먼저 출력하고, 그 뒤에 새로 놓아야 하는 도로의 최소 개수를 출력한다. 여기서 xx는 테스트 케이스 번호로 1부터 시작한다.

예제1

  1. 예제 1

    입력
    3
2
2
0 1
0 1
3
3
1 2
1 2
2 1
4
5
0 1
2 0
0 3
1 2
3 1
    예상 출력
    Case #1: 0
Case #2: 1
Case #3: 1