Given an undirected weighted connected graph, the weight of each edge of this graph is a positive integer. Each time you can choose an edge and then change its weight into any other positive integer. Here is the problem; how many edges you need to choose in order to make the total weight of each bond of this graph is even. The number of the edges you choose should be as small as possible.
An edge cut E of a graph G is a set of edges of G and the graph G would be disconnected after deleting all the edges of E.
A bond of a graph is a minimal nonempty edge cut which means that it’s an edge cut but any proper subsets of it is not an edge cut.
The first line of the data is an integer T (1 <= T <= 100), which is the number of the text cases.
Then T cases follow, each case starts with two number N, M (2 <= N <= 18, N-1 <= M <= N*(N-1)/2) describe the number of the vertexes and the number of the edges of the given graph. Then goes m lines, each line contains three different integers x, y, s (1 <= x <= N, 1 <= y <= N, 1 <= s <= 10) which means that there is an edge between x and y, its weight is s. Note that the given graph is connected and there is at most one edge between every two vertexes.
In 95% of the test dates, N <= 6.
For each case, output the case number first, then output the number of the chosen edges. This number should be as small as possible.
See the sample input and output for more details.
5 3 3 1 2 1 1 3 1 2 3 1 3 3 1 2 1 1 3 1 2 3 2 4 6 1 2 1 1 3 2 1 4 2 2 3 1 2 4 2 3 4 1 4 6 1 2 1 1 3 2 1 4 2 2 3 2 2 4 2 3 4 1 4 3 1 2 1 2 3 1 3 4 1
Case 1: 0 Case 2: 1 Case 3: 1 Case 4: 2 Case 5: 3