e-olymp
Competitions

НВП + DSU

Road Removal

You are given a network with n cities and m bidirectional roads connecting these cities. The first k cities are important. You need to remove the minimum number of roads such that in the remaining network there are no cycles that contain important cities. A cycle is a sequence of at least three different cities such that each pair of neighboring cities are connected by a road and the first and the last city in the sequence are also connected by a road.

Input

The first line contains the number of test cases t (1t20).

Each case begins with a line containing integers n, m and k (1n10000, 1m50000, 1kn), which represent the number of cities, the number of roads and the number of important cities, respectively. The cities are numbered from 0 to n-1, and the important cities are numbered from 0 to k-1. The following m lines contain two integers ai and bi, 0i < m, that represent two different cities connected by a road.

It is guaranteed that 0ai, bi < n and aibi. There will be at most one road between two cities.

Output

For each of the test cases numbered in order from 1 to t, output "Case #i: " followed by a single integer, the minimum number of roads that need to be removed such that there are no cycles that contain an important city.

Example

In the first example, we have n = 5 cities that are connected by m = 7 roads and the cities 0 and 1 are important. We can remove two roads connecting (0, 1) and (1, 2) and the remaining network will not contain cycles with important cities. Note that in the remaining network there is a cycle that contains only non-important cities, and that there are also multiple ways to remove two roads and satisfy all conditions. One cannot remove only one road and destroy all cycles that contain important cities.

Time limit 1 second
Memory limit 64 MiB
Input example
2
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4
8 12 2
0 2
0 4
0 5
2 3
2 7
3 1
3 4
4 6
5 6
5 7
6 1
7 1
Output example
Case #1: 2
Case #2: 4