Ağacda oyun
Алиса və Bob istiqamətsiz ağacda oyun oynayırlar. İlk gedişi edən Алиса ağacın istənilən zirvəsini işarələyə bilər. Sonra oyunçular növbə ilə hərəkət edirlər. Hər oyunçu öz gedişində SON işarələnmiş zirvə ilə qonşu olan bir zirvəni seçib işarələyə bilər. Oyunçu artıq işarələnmiş zirvəni seçə bilməz. Əgər oyunçu zirvə seçə bilmirsə, o məğlub olur.
Hər iki oyunçunun optimal oynadığını nəzərə alaraq, oyunun başlanğıc vəziyyətinə görə qalibi müəyyən edin.
Giriş verilənləri
Birinci sətir testlərin sayını T ehtiva edir. Sonra testlərin təsviri gəlir. Hər testin birinci sətiri ağacdakı zirvələrin sayını N ehtiva edir. Növbəti N-1 sətirin hər biri a və b arasında boşluqla ayrılmış iki tam ədəd ehtiva edir, bu da a və b arasında bir kənarın mövcud olduğunu göstərir. (1 ≤ a, b ≤ N).
Məlumdur ki, T ≤ 25, N ≤ 50000.
Çıxış verilənləri
Çıxış T sətir ehtiva edir. Hər test üçün ayrıca sətirdə "Alice" əgər Алиса qalib gəlirsə və "Bob" əks halda çıxarılmalıdır. [dırnaq işarələri çıxarılmır].