Giacint

Northwestern Europe Routing Company (NWERC) şirkətində yeni işçi olaraq simsiz şəbəkə arxitekturaları üzərində çox düşünürsünüz. Son vaxtlar hər bir şəbəkə düyününü bir neçə şəbəkə interfeysi kartı (ŞİK) ilə təmin edən çoxkanallı mesh şəbəkə arxitekturası (Hiasint adlanır) haqqında məlumat əldə etmisiniz. Bu arxitektura şəbəkənin keçirmə qabiliyyətini artırır. Hər bir şəbəkə adapteri üçün kanal tezliyini seçə bilərsiniz. Əlaqə qurmaq üçün bir-birinin əhatə dairəsində olan hər iki şəbəkə düyünü ən azı bir ümumi tezliyə malik olmalıdır. Şəbəkədə istifadə olunan tezliklərin ümumi sayı maksimum olduqda, teorik keçirmə qabiliyyəti optimal olur.

NWERC-də rəhbərləriniz sizdən ŞİK tezliklərinin təyin edilməsi prosedurunu elə həyata keçirməyinizi istəyirlər ki, istifadə olunan tezliklərin sayı maksimum olsun və bütün qonşu düyün cütləri üçün məhdudiyyətlər nəzərə alınsın. Tezlik istifadə olunmuş sayılır, əgər bir-birinin əhatə dairəsində olan hər hansı bir düyün cütü bu tezliyi paylaşırsa. Siz məşğul olacağınız mesh şəbəkədə hər bir düyün dəqiq iki şəbəkə kartı ilə təchiz olunub (yəni hər bir düyün ən çox iki tezlik istifadə edə bilər). NWERC-də yeni olduğunuz üçün rəhbərləriniz işinizi asanlaşdırmaq məqsədilə şəbəkə sxemlərini məhdudlaşdırırlar: şəbəkə qrafiki ağac formasında olacaq.

Giriş Məlumatları

Aşağıdakılardan ibarətdir:

• bir sıra n (2 ≤ n ≤ 10000) - şəbəkədəki düyünlərin sayını ehtiva edir;

• n - 1 sıra, hər biri iki ədəd i və j ehtiva edir, burada 1 ≤ i, j ≤ n, bu isə i və j düyünlərinin bir-birinin əhatə dairəsində olduğunu bildirir.

Çıxış Məlumatları

Hər bir 2n ŞİK üçün tezlik təyinatını çıxarın ki, bütün qonşu düyünlər əlaqə qura bilsin və istifadə olunan tezliklərin sayı maksimum olsun. Siz n sıra çıxarmalısınız, burada i-ci sıra i şəbəkə düyününün iki tezliyini ehtiva edir. Etibarlı tezliklər 10^9-dan kiçik olan qeyri-mənfi tam ədədlərdir.