Under construction

Still being built. Things may change

Battlefield

Time limit5sMemory limit512 MB

Summary
Compute the fewest new roads needed so one closed tour can traverse every road exactly once.
Level

Medium7 of 10

Topics
Graph, Math
Solved
No attempts yet

Problem

A battlefield is made of NN cities and RR bidirectional roads. You want to pick any city CC you like, start there, travel every road exactly once, and finish back at CC.

If no such trip exists, you build new roads. A new road also has to be travelled exactly once during the trip. Find the smallest number of new roads that makes the trip possible.

Several roads may connect the same pair of cities. You may build a new road between any two different cities, whether or not a road already connects them. A city that no road touches does not have to be visited.

Input

The first line contains the number of test cases TT. TT test cases follow, each in this form.

  • One line with the number of cities NN.
  • One line with the number of roads RR.
  • RR lines, one per road. Each line has two integers AA and BB separated by one space, the two endpoints of that road. AA and BB are different and satisfy 0≤A,B<N0 \le A, B < N.

Limits

  • 1≤T≤301 \le T \le 30
  • 2≤N≤10002 \le N \le 1000
  • 1≤R≤151 \le R \le 15

Output

For each test case, print one line with Case #x: followed by the smallest number of new roads. xx is the number of the test case.

Examples2

  1. Example 1

    Input
    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
    Expected output
    Case #1: 0
Case #2: 1
Case #3: 1

  2. Example 2

    Input
    1
2
1
0 1
    Expected output
    Case #1: 1