Saatlı ağac

Yeni Fermer Conun anbarı $n$ otaqdan ibarətdir, $1$-dən $n$-ə qədər nömrələnmiş və $n-1$ dəhlizdən ibarətdir. Hər bir dəhliz bir cüt otağı birləşdirir ki, hər hansı bir otaqdan digərinə dəhlizlər vasitəsilə keçmək mümkün olsun.

Anbarda hər otağın divarında standart $1$-dən $12$-ə qədər rəqəmlərlə saat var. Lakin bu saatlarda yalnız bir əqrəb var və o, həmişə tam bir rəqəmi göstərir (heç vaxt iki rəqəm arasında göstərmir).

İnek Bessi bütün saatları sinxronlaşdırmaq istəyir ki, hamısı $12$-ni göstərsin. Lakin öz inək düşüncəsi ilə, hər dəfə bir otağa daxil olanda, əqrəbi bir mövqe irəli çəkir. Məsələn, əgər əqrəb $5$-i göstərirdisə, Bessi onu $6$-ya çəkir. Əgər saat $12$-ni göstərirdisə, o, əqrəbi $1$-ə çəkir. Əgər Bessi bir otağa bir neçə dəfə daxil olursa, hər girişdə əqrəbi çəkir.

Bessi anbarın bütün saatlarını $12$-yə qurmaq üçün hansı otaqlardan səyahətə başlaya biləcəyini müəyyən edin. Qeyd edək ki, Bessi yolun başlanğıcında başlanğıc otağında əqrəbi çəkmir və hər sonrakı girişdə çəkir. Əqrəblər öz-özünə hərəkət etmir. Bessi dəhlizə daxil olduqda, sonuna qədər getməli və dəhlizin sonunda otağa daxil olmalıdır. O, dəhliz içində geri dönüb çıxdığı otağa yenidən daxil ola bilməz.

Giriş verilənləri

Birinci sətir $n(2\le n\le 2500)$ sayını ehtiva edir. Növbəti sətir hər biri $[1,12]$ intervalında olan $n$ tam ədədi ehtiva edir, hər biri hər otaqdakı əqrəblərin başlanğıc mövqelərini göstərir. Növbəti $n-1$ sətir hər biri $[1,n]$ intervalında olan iki tam ədəd $a$ və $b$ ehtiva edir və bu dəhlizin birləşdirdiyi otaqların nömrələrini göstərir.

Çıxış verilənləri

Bessi bütün saatları $12$-yə qurmaq üçün səyahətə başlaya biləcəyi otaqların sayını çıxarın.

Nümunələr

Bu nümunədə Bessi yalnız $2$-ci otaqdan (və sonra məsələn, $1,2,3,2$ və nəhayət $4$ otağına keçərək) bütün saatları $12$-yə qura bilər.