Ağacda Yollar#3103
Sizə bir ağac verilir (dairəsi olmayan əlaqəli qraf), burada kənarlar yönəldilmişdir. Sizin vəzifəniz istənilən bir düyündən digərinə keçidi təmin etmək üçün minimum sayda xüsusi yol əlavə etməkdir. Xüsusi yollar üçün qaydalar belədir:
Xüsusi yol, kənarların (ağacdan götürülən) və düyünlərin ardıcıllığından ibarətdir.
Xüsusi yolda kənarların istiqaməti ağacdakı istiqamətlə tam əksinə olmalıdır.
Xüsusi yolda bir düyün və ya kənar ən çox bir dəfə istifadə oluna bilər.
Müxtəlif xüsusi yollar ümumi düyün və ya kənarlar paylaşa bilər.
Məsələn, aşağıdakı şəkildə bir ağac göstərilmişdir. Qara oxlar kənarları və onların istiqamətini göstərir, 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) olur. Alternativ olaraq, 3-1 yolunun yerinə 3-1-0 əlavə edə bilərsiniz. Qayda 2-yə görə 1-3 və ya 0-1-2 kimi bir yol əlavə edə bilməzsiniz, qayda 1-ə görə isə 0-2 və ya 2-3-0 mümkün deyil.
Giriş bir tam ədəd T () ilə başlayır — testlərin sayı.
Hər bir testin əvvəlində bir tam ədəd N (2 \leq N \leq 20000) verilir, burada — düyünlərin sayıdır. Düyünlər 0-dan N-1-ə kimi nömrələnir. Sonrakı N-1 sətrin hər birində iki tam ədəd u v (0 \leq u, v < N, u \neq v) verilir; bu o deməkdir ki, -dan -yə yönəlmiş bir kənar var.
Hər test üçün testin nömrəsini və istənilən düyündən istənilən digərinə keçidi təmin etmək üçün tələb olunan minimum xüsusi yolların sayını çap edin.
Nümunə 1