C. Замын хөгжил

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландад $n$ хот болон $n - 1$ хос чиглэлтэй зам байна. Зам бүр хос хотыг холбох ба та дурын хотоос өөр дурын хотруу зөвхөн өгөгдсөн замуудаар очиж болно.

Хот бүрт яг нэг ширхэг засварын бригад байгаа. Нэг замыг засахын тулд та уг замаар холбогдсон хоёр хотын бригадуудыг нэг өдөр зэрэг ажиллуулах шаардлагатай. Хоёр бригад бүтэн өдрийн турш нэг л замыг засах ба тус өдөр бусад замуудыг засах боломжгүй. Гэвч засварын бригад тухайн өдөр юу ч хийж чадахгүй.

Бүх замыг засахад шаардлагатай өдрүүдийн хамгийн бага тоог тодорхойл. Бригадууд анх байсан хотуудаа сольж чадахгүй.

Оролт

Оролтын эхний мөрөнд эерэг бүхэл тоон утга $n$ ($2 ≤ n ≤ 200 000$) байх ба Берланд дахь хотуудын тоо.

Дараагийн $n - 1$ мөр бүрт хоёр бүхэл тоон утга $u_{i}$, $v_{i}$ байх ба $i$-р зам $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$) хотыг холбоно гэсэн үг.

Гаралт

Эхлээд Берланд дахь бүх замыг засахад шаардлагатай өдрүүдийн хамгийн бага тоо болох $k$ тоог хэвлэ.

Дараагийн $k$ мөрөнд $k$ өдрийн өдөр бүр засагдах ёстой замуудын тайлбарыг хэвлэ. $i$-р мөрөнд эхний $i$-р өдөр засагдах ёстой замуудын тоо $d_{i}$-г хэвлэх ба үргэлжлүүлэн зайгаар тусгаарласан $d_{i}$ бүхэл тоон утгуудыг хэвлэх ба энэ нь $i$-р өдөр засагдах ёстой замын тоо байна. Замууд оролтонд өгсөн дарааллаараа нэгээс эхлэн дугаарлагдсан.

Хэрвээ хэд хэдэн боломж байвал та алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4
1 2
3 4
3 2
Гаралт
2
2 2 1
1 3
Оролт
6
3 4
5 4
3 2
1 3
4 6
Гаралт
3
1 1 
2 2 3 
2 4 5 

Тэмдэглэл

Эхний жишээн дээр та бүх замыг хоёр өдрийн дотор засч чадна, жишээлбэл, та эхний өдөр $1$ болон $2$-р замыг засах бол хоёр дахь өдөр $3$-р замыг засна.

Сэтгэгдлүүдийг ачааллаж байна...