eolymp
bolt
Try our new interface for solving problems
Məsələlər

Yolların ləğvi

Yolların ləğvi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

n şəhərdən və bu şəhərləri birləşdirən m ikiistiqamətli yollardan ibarət şəbəkə var. İlk k şəhər əhəmiyyətlidir. Sizə elə minimal sayda yolları ləğv etmək lazımdır ki, qalan şəbəkədə əhəmiyyətli şəhərlərdən keçən dövrlər olmasın. Dövr elə ardıcıllıqdır ki, ən azı elə üç şəhər vardır ki, hər bir qonşu şəhərlər cütlüyü öz aralarında yolla birləşmiş olsun, birinci və sonuncu şəhərlər də birləşmiş olsunlar.

Giriş verilənləri

Birinci sətir testlərin t (1t20) sayını ehtiva edir.

Hər bir test üç tam n, mk (1n10000, 1m50000, 1kn) ədədlərini – şəhərlərin, yolların və əhəmiyyətli şəhərlərin sayını ehtiva edən sətirlə başlayır. Şəhərlər 0-dan n–1-ə qədər ədədlərlə nömrələnir. Növbəti m sətrin hər biri yolla birləşdirilmiş müxtəlif şəhərlərin nömrələrini əks etdirən iki a_ib_{i }(0i < m) tam ədədlərini ehtiva edir.

Məlumdur ki, 0a_i, b_i < na_ib_i. İki şəhər arasında yolların sayı birdən çox deyil.

Çıxış verilənləri

1-dən t-yə qədər nömrələnmiş hər bir test üçün "Case #i: " sətrini, ardına da, tam ədədi – ləğv ediləcək minimal sayda yolların sayını verin (heç olmazsa bir vacib şəhərin belə daxil olduğu dövrün olmadığı yollar ləğv edilməlidir).

Misal

Birinci misalda n = 5 şəhər və m = 7 yol vardır. 01 şəhərləri əhəmiyyətlidir. (0, 1) və (1, 2) yollarını silmək olar, bundan sonra qalan şəbəkə vacib şəhərlər olan dövrlər ehtiva etməyəcək. Qeyd edək ki, qalan şəbəkədə vacib olmayan şəhərlərdən keçən dövr var. Məsələdə qoyulan tələbləri yerinə yetirmək üçün iki tili silməyin bir neçə üsulu vardır. Bir tili silməklə vacib şəhərlərdən keçən bütün dövrləri ləğv etməyə ehtiyac yoxdur.

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
Case #1: 2
Case #2: 4