e-olymp

Удаление дорог

Имеется сеть из n городов и m двунаправленных дорог, соединяющих эти города. Первые k городов считаются важными. Вам необходимо так удалить наименьшее количество дорог, чтобы в оставшейся сети не было циклов, проходящих через важные города. Цикл представляет собой последовательность по крайней мере трех таких разных городов, что каждая пара соседних городов связана между собой дорогой, а первый и последний город также соединены дорогой.

Входные данные

Первая строка содержит количество тестов t (1t20).

Каждый тест начинается строкой, содержащей три целых числа n, m и k (1n10000, 1m50000, 1kn) - количество городов, дорог и важных городов соответственно. Города пронумерованы числами от 0 до n - 1, а важные города пронумерованы числами от 0 до k - 1. Каждая из следующих m строк содержит два целых числа ai и bi, 0i < m, описывающих номера разных городов, соединенных дорогой.

Известно, что 0ai, bi < n и aibi. Между двумя городами существует не более одной дороги.

Выходные данные

Для каждого теста, пронумерованного числами от 1 до t, вывести строку "Case #i: ", за которой следует целое число - наименьшее количество дорог, подлежащих удалению таким образом, чтобы не осталось ни одного цикла, в который входил хотя бы один важный город.

Пример

В первом примере имеется n = 5 городов и m = 7 дорог, города 0 и 1 являются важными. Можно удалить дороги (0, 1) и (1, 2), после чего оставшаяся сеть не будет содержать циклов, содержащих важные города. Отметим, что в оставшейся сети присутствует цикл, проходящий через неважные города. Для выполнения требования задачи существует несколько способов удаления двух ребер. Удалением одного ребра нельзя уничтожить все циклы, проходящие через важные города.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
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
Выходные данные
Case #1: 2
Case #2: 4