Ağacda Yollar
Ağac (dövrü olmayan bağlı qraf) verilib və bu ağacın kənarları müəyyən səbəblərə görə istiqamətlidir. Sizin vəzifəniz, ağacda hər hansı bir düyündən digərinə keçə bilmək üçün minimum sayda xüsusi yollar əlavə etməkdir. Xüsusi yollar üçün qaydalar aşağıda verilmişdir:
Xüsusi yol, bəzi ardıcıl kənarlardan (ağacdan) və düyünlərdən ibarətdir.
Xüsusi yolda kənarlar ağacda olduğu kimi əks istiqamətdə olmalıdır.
Xüsusi yolda bir düyün və ya kənar ən çox bir dəfə ziyarət edilə bilər.
Bir neçə xüsusi yol ümumi düyünlərə və ya kənarlara malik ola bilər.
Məsələn, aşağıdakı şəkildə ağac təsvir edilib; qara oxlar kənarları və onların istiqamətlərini, dairələr isə düyünləri göstərir. Bu halda iki xüsusi yol tələb olunur. Bir yol 2-1-0 (yaşıl ox), digəri isə 3-1 (mavi ox) olmalıdır. 3-1 yolunun əvəzinə 3-1-0 da əlavə edə bilərsiniz. Qayda 2-yə görə 1-3 və ya 0-1-2 kimi yollar əlavə edə bilməzsiniz. Qayda 1-ə görə 0-2 və ya 2-3-0 əlavə edə bilməzsiniz.
Giriş verilənləri
Giriş bir tam ədəd T (≤ 30) ilə başlayır, bu da test hallarının sayını göstərir.
Hər bir hal bir tam ədəd N (2 ≤ N ≤ 20000) olan sətirlə başlayır, burada N düyünlərin sayını göstərir. Düyünlər 0-dan N-1-ə qədər nömrələnir. Növbəti N-1 sətirin hər biri iki tam ədəd u v (0 ≤ u, v < N, u ≠ v) ehtiva edir, bu da u-dan v-yə bir kənarın olduğunu bildirir.
Çıxış verilənləri
Hər bir hal üçün, hal nömrəsini və hər hansı bir düyündən digərinə keçmək mümkün olması üçün tələb olunan minimum xüsusi yolların sayını çap edin.