Öz İşinizi Mədənçiliklə Əldə Etmək#2288
John Digger böyük illudium phosdex mədəninin sahibidir. Mədən bir neçə böyük qovşağın birləşdiyi tunellərdən ibarətdir. Bəzi sahiblərdən fərqli olaraq, Digger işçilərinin rifahına önəm verir və mədən planlanmasından narahatdır. Xüsusilə, o, elə bir qovşaq ola biləcəyindən narahatdır ki, onun çökməsi halında mədənın bir hissəsindəki işçilər digərlərindən təcrid oluna bilər (bildiyiniz kimi, illudium phosdex çox qeyri-sabitdir). Bunu qarşısını almaq üçün, o, qovşaqlardan səthə xüsusi təxliyə şaxtaları qurmaq istəyir. Hər bir qovşaqda təxliyə şaxtası qura bilərdi, lakin Digger işçilərini o qədər də sevmir. Bunun əvəzinə, elə minimum sayda təxliyə şaxtası qurmaq istəyir ki, istənilən qovşaq çöksə, həyatda qalan bütün işçilər səthə çıxış yolunu tapa bilsinlər.
Belə bir proqram yazın ki, minimum neçə təxliyə şaxtasına ehtiyac olduğunu və bu şaxtaları neçə cür qurmaq yollarının olduğunu hesablaya bilsin.
Girişdə bir neçə test halı verilir. Hər test halının ilk sətrində müsbət tam ədəd (N \leq 5 \cdot 10^4) verilir, bu da mədən tunellərinin sayını göstərir. Daha sonra sətirdə hərəsində ayrı-ayrı iki tam ədəd və verilir, burada və qovşaq nömrələridir. Qovşaqlar -dən başlayaraq ardıcıl şəkildə nömrələnir. Hər iki qovşağı birləşdirən ən çox bir tunel olur. Hər bir tunel dəsti bir bağlı vahid təşkil edir (yəni, istənilən qovşaqdan digərinə keçmək mümkündür).
Sonuncu test halından sonra yalnız bir sıfırdan ibarət bir sətir gəlir.
Hər bir test halı üçün əvvəlcə test halının nömrəsini çıxışa verin, sonra isə minimum lazım olan təxliyə şaxtalarının sayını və bu şaxtaları qurmaq yollarının ümumi sayını yazın. Qəbul edin ki, cavab nümunəsi imzalı -bit tam ədədə yerləşir.
Nümunəyə uyğun çıxışı izləyin.
Nümunə 1