Öz İşinizi Mədənçiliklə Əldə Etmək
John Digger böyük bir illudium fosdeks mədəninin sahibidir. Mədən, müxtəlif böyük qovşaqlarda birləşən bir sıra tunellərdən ibarətdir. Digər sahiblərdən fərqli olaraq, Digger işçilərinin rifahına əhəmiyyət verir və mədənin planı ilə bağlı narahatdır. Xüsusilə, o, çökmə halında bir qovşağın mədənin bir hissəsindəki işçiləri digər işçilərdən ayıra biləcəyindən narahatdır (bildiyiniz kimi, illudium fosdeks çox qeyri-sabitdir). Buna qarşı, o, qovşaqlardan səthə xüsusi qaçış şaxtaları quraşdırmaq istəyir. Hər bir qovşaqda bir qaçış şaxtası qura bilərdi, amma Digger işçilərinə bu qədər əhəmiyyət vermir. Bunun əvəzinə, o, minimum sayda qaçış şaxtası quraşdırmaq istəyir ki, hər hansı bir qovşaq çökərsə, qovşaq çökməsindən sağ çıxan bütün işçilərin səthə bir yolu olsun.
Minimum sayda qaçış şaxtasını və bu minimum sayda qaçış şaxtasının quraşdırıla biləcəyi ümumi yolların sayını hesablamaq üçün bir proqram yazın.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər bir halın ilk sətri müsbət tam ədəd N (N ≤ 5·10^4) ehtiva edir ki, bu da mədən tunellərinin sayını göstərir. Bundan sonra, hər biri iki fərqli tam ədəd s və t ehtiva edən N sətir gəlir, burada s və t qovşaq nömrələridir. Qovşaqlar ardıcıl olaraq 1-dən başlayaraq nömrələnir. Hər bir qovşaq cütü ən çox bir tunellə birləşdirilir. Hər bir mədən tunelləri dəsti bir bağlı vahid təşkil edir (yəni, hər hansı bir qovşaqdan digərinə keçmək mümkündür).
Son test halından sonra tək sıfır ehtiva edən bir sətir gəlir.
Çıxış verilənləri
Hər bir test halı üçün, onun hal nömrəsini, mədən tunelləri sistemi üçün lazım olan minimum qaçış şaxtalarının sayını və bu qaçış şaxtalarının quraşdırıla biləcəyi ümumi yolların sayını göstərin. Nəticənin imzalı 64-bit tam ədədə sığacağını qəbul edə bilərsiniz.
Nümunə çıxışın formatına əməl edin.