만드는 중입니다

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

전장

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

요약
모든 도로를 정확히 한 번씩 지나 원래 도시로 돌아오는 여행이 가능하도록 추가할 도로 수의 최솟값을 구합니다.
난이도

보통10점 중 7점

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

문제

전장은 도시 NN개와 양방향 도로 RR개로 이루어진다. 원하는 도시 CC 하나를 골라 출발해서 모든 도로를 정확히 한 번씩 지나고 다시 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≤151 \le R \le 15

출력

각 테스트 케이스마다 한 줄에 Case #x: 를 출력하고, 그 뒤에 새로 놓아야 하는 도로의 최소 개수를 출력한다. xx는 테스트 케이스 번호다.

예제2

  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

  2. 예제 2

    입력
    1
2
1
0 1
    예상 출력
    Case #1: 1