Ağacda oyun

Alice və Bob ağac üzərində bir oyun oynayırlar. Başlanğıcda bütün zirvələr ağ rəngdədir.

Alice oyuna başlayır. O, istənilən zirvəni seçir və onun üzərinə fişka qoyur, bu zirvə qara olur. Sonra oyunçular növbə ilə hərəkət edirlər. Hər hərəkətdə oyunçu fişkanı cari mövqedən qara olmayan bir əcdada və ya nəslə köçürür. Bu zirvə də qara olur. Fişkanı köçürə bilməyən oyunçu məğlub olur.

Oyunu kim qazanacaq?

Uzvun v kök ağacında əcdadı, v və ağacın kökü arasında olan hər hansı bir uzvudur.

Uzvun v kök ağacında nəslidir, w uzvu elədir ki, v uzvu w və ağacın kökü arasında yerləşir.

Ağacın kökü 1 zirvəsində yerləşir.

Giriş məlumatları

Birinci sətir zirvələrin sayını n (1 ≤ n ≤ 10^5) ehtiva edir.

Növbəti n - 1 sətirin hər biri iki tam ədəd u və v (1 ≤ u, v ≤ n) ehtiva edir - ağacın kənarları. Onların ağac yaratdığı təmin edilir.

Çıxış məlumatları

Əgər Alice qazanırsa, "Alice" çıxarın. Əks halda "Bob" çıxarın.

İzah

Birinci nümunədə ağac düz xətt şəklindədir və 4 zirvəyə malikdir, buna görə Bob həmişə sonuncu ağ zirvəni seçə bilər.

İkinci nümunədə Alice üçün optimal strategiya 3 üzərinə fişka qoymaqdır. Bu zirvə qara olur. Bob 1 zirvəsini seçməlidir. Alice 4, 5, 6 və ya 7 zirvələrindən birini seçə bilər. Bob yalnız 2 zirvəsini seçə bilər. Alice 2-nin ağ övladlarından birini seçir və Bob hərəkət edə bilmir.