eolymp
bolt
Try our new interface for solving problems
Problems

Road Removal

Road Removal

Time limit 1 second
Memory limit 64 MiB

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 data

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 a_i and b_i, 0i < m, that represent two different cities connected by a road.

It is guaranteed that 0a_i, b_i < n and a_ib_i. There will be at most one road between two cities.

Output data

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.

Examples

Input example #1
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 #1
Case #1: 2
Case #2: 4