Masala C

Siz yangi barpo etilgan davlatning bosh me'morisiz. Davlatda \(N\) ta shahar bor va ular \(N - 1\) ta ikki tomonlama yo'l bilan bog'langan. Shaharlar tizimi daraxt strukturasini hosil qiladi (ya'ni, ixtiyoriy ikki shahar orasida yagona yo'l mavjud).

Qirol davlatni boshqarish uchun har bir shaharga bir nafardan amaldor tayinlashni buyurdi. Amaldorlarning darajalari ingliz alifbosining bosh harflari bilan belgilanadi: 'A', 'B', ..., 'Z'. Bu yerda 'A' eng yuqori daraja, 'B' esa undan keyingi o'rinda turadi va hokazo.

Qirolning talabi quyidagicha:

Agar ikki xil \(u\) va \(v\) shaharlariga bir xil darajali amaldorlar tayinlangan bo'lsa, u holda \(u\) va \(v\) shaharlarini bog'lovchi yagona oddiy yo'lda kamida bitta yuqoriroq darajali amaldor o'tirgan shahar bo'lishi shart.

Eslatma: Masalan, ikki shaharda ham 'C' darajali amaldor bo'lsa, ular orasidagi yo'lda kamida bitta 'A' yoki 'B' darajali amaldor bo'lishi kerak.

Sizning vazifangiz — Qirolning talabini qondiradigan tarzda amaldorlarni shaharlarga taqsimlash.

Birinchi qatorda shaharlar sonini ifodalovchi \(N\) butun soni beriladi \((1 ≤ N ≤ 10^5)\).

Keyingi \(N - 1\) ta qatorda ikkitadan butun son \(u_i\) va \(v_i\) beriladi \((1 ≤ u_i, v_i ≤ N)\). Bu sonlar \(u_i\) va \(v_i\) shaharlari o'rtasida yo'l borligini bildiradi.

Yagona qatorda masala javobini chiqaring. \(i\)-harf \(i\)-shaharga tayinlangan amaldor darajasi.