Имеется сеть из n городов и m двунаправленных дорог, соединяющих эти города. Первые k городов считаются важными. Вам необходимо так удалить наименьшее количество дорог, чтобы в оставшейся сети не было циклов, проходящих через важные города. Цикл представляет собой последовательность по крайней мере трех таких разных городов, что каждая пара соседних городов связана между собой дорогой, а первый и последний город также соединены дорогой.
Первая строка содержит количество тестов t (1 ≤ t ≤ 20).
Каждый тест начинается строкой, содержащей три целых числа n, m и k (1 ≤ n ≤ 10000, 1 ≤ m ≤ 50000, 1 ≤ k ≤ n) - количество городов, дорог и важных городов соответственно. Города пронумерованы числами от 0 до n - 1, а важные города пронумерованы числами от 0 до k - 1. Каждая из следующих m строк содержит два целых числа a_i и b_i, 0 ≤ i < m, описывающих номера разных городов, соединенных дорогой.
Известно, что 0 ≤ a_i, b_i < n и a_i ≠ b_i. Между двумя городами существует не более одной дороги.
Для каждого теста, пронумерованного числами от 1 до t, вывести строку "Case #i: ", за которой следует целое число - наименьшее количество дорог, подлежащих удалению таким образом, чтобы не осталось ни одного цикла, в который входил хотя бы один важный город.
Пример
В первом примере имеется n = 5 городов и m = 7 дорог, города 0 и 1 являются важными. Можно удалить дороги (0, 1) и (1, 2), после чего оставшаяся сеть не будет содержать циклов, содержащих важные города. Отметим, что в оставшейся сети присутствует цикл, проходящий через неважные города. Для выполнения требования задачи существует несколько способов удаления двух ребер. Удалением одного ребра нельзя уничтожить все циклы, проходящие через важные города.