Видаленя доріг
Є мережа з 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), після чого залишиться мережа, яка не буде містити циклів, що проходять через важливі міста. Відмітимо, що у залишковій мережі існує цикл, що проходить через неважливі міста. Для виконання вимоги задачі існує декілька способів видалення двох ребер. Видаленням одного ребра неможливо знищити усі цикли, які проходять через важливі міста.