Təhlükəsiz uçuş
Büdcə məhdudiyyətləri səbəbindən, casuslar belə şəhərlər arasında səyahət etmək üçün kommersiya aviaşirkətlərindən istifadə etməlidirlər. Bu səyahət üsulu casuslar üçün rahat olsa da, bir problem yaradır: casus pilota etibar etməlidir, yəni uçuş zamanı təhlükəsiz olduğunu təmin etməlidir. Daha da çətin olanı, bəzi şəhər cütləri arasında birbaşa reyslərin olmamasıdır, bu halda casus bir neçə reyslə səyahət etməli və nəticədə bir neçə pilota etibar etməlidir!
Etibar məsələlərini minimuma endirmək üçün sizdən kömək istənilib. Mövcud uçuş cədvəlinə əsasən, casusun bütün şəhərlər arasında təhlükəsiz səyahət edə bilməsi üçün etibar edilməli olan ən az pilot dəstini tapmaq lazımdır.
Giriş məlumatları
Birinci sətir testlərin sayını ehtiva edir, bu, 100-dən çox deyil. Daha sonra hər bir test üçün:
Bir sətirdə şəhərlərin sayı n (2 ≤ n ≤ 1000) və pilotların sayı m (1 ≤ m ≤ 10000).
m sətir, hər birində a və b (1 ≤ a, b ≤ n, a ≠ b) rəqəmləri: pilot şəhərlər arasında a və b istiqamətində uçur.
Şəhərlər arasında bir və ya bir neçə uçuşdan istifadə edərək səyahət etmək mümkündür. Qraf əlaqəlidir.
Çıxış məlumatları
Hər bir test üçün ayrı-ayrı sətirdə casusun hər hansı bir şəhər cütü arasında səyahət edə bilməsi üçün etibar edilməli olan ən az pilot sayını çıxarın.