D. T-задрал

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

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

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

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

Танд $n$ зангилаатай чиглэлгүй мод $s$ байна. Таны ажил бол уг модонд зориулсан тохиромжтой T-задралыг байгуулах юм. T-задралыг дараах байдлаар тодорхойлье.

$s$-н бүх зангилааг агуулсан бүрдлийг $v$ гэж тэмдэглэе. Зангилаанууд нь $v$-н хоосон биш дэд бүрдэл байх буюу $x_{i}$ байх $t$ чиглэлгүй модыг авч үзье. Хэрвээ дараах нөхцөлүүд биелэж байвал $t$ мод нь $s$-н T-задрал болно:

  1. бүх $x_{i}$-н нэгдэл нь $v$-тэй тэнцүү байх;
  2. $s$-н дурын $(a, b)$ ирмэгийн хувьд $a$ ба $b$-г хоёуланг нь агуулсан $t$ модны зангилаа оршин байх;
  3. хэрвээ $t$ модны $x_{i}$ ба $x_{j}$ зангилаанууд нь $s$ модны $a$ зангилааг агуулж байвал $x_{i}$-с $x_{j}$ хүртэлх зам дээрх $t$-н бүх зангилаа мөн $a$-г агуулна. Мөн энэ нөхцөл нь дараах нөхцөлтэй ижил: $s$ модны $a$ зангилааг агуулж байгаа бүх $t$-н зангилаанууд $t$ модны холбогдсон дэд мод үүсгэнэ.

Мэдээж $s$ модны Т-задрал байх ялгаатай олон $t$ мод байгаа. Жишээлбэл $v$ бүрдэлтэй тэнцүү нэг зангилаатай мод Т-задрал байж болно.

$x_{i}$ зангилаанд агуулагдаж байгаа $s$ модны зангилаануудын тоо буюу $x_{i}$ зангилааны хэмжээг олцгооё. $t$ модон дахь хамгийн их хэмжээтэй зангилааг сонгоё. Энэ зангилааны жинг $w$ гэе. Тэгээд $t$ T-задралын жин нь $w$ байна. Хамгийн тохиромжтой Т-задрал нь хамгийн бага жинтэй байна.

Таны ажил бол өгөгдсөн $s$ модны хамгийн тохиромжтой Т-задралыг олох буюу хамгийн бага тооны зангилаатайг нь олно гэсэн үг юм.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ $(2 ≤ n ≤ 10^{5})$ байх ба $s$ модны зангилааны тоо юм.

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

$s$ модны зангилаанууд 1-с $n$ хүртэл дугаарлагдсан гэж үз. $s$ нь мод байх нь тодорхой.

Гаралт

Эхний мөрөнд нэг бүхэл тоо $m$ байх ба шаардлагатай Т-задралын зангилаануудын тоо юм.

Дараагийн $m$ мөрөнд Т-задралын зангилаануудын тайлбар байна. $i$-р $(1 ≤ i ≤ m)$ мөрөнд Т-задралын $x_{i}$ зангилааны тайлбар байна. $x_{i}$ зангилаа бүрийн тайлбар нь $x_{i}$ зангилаанд агуулагдсан анхны $s$ модны зангилаануудын тоог илэрхийлэх $k_{i}$ бүхэл тоогоор эхлэх ёстой. Үүний дараа та зайгаар тусгаарлагдсан $k_{i}$ бүхэл тоог хэвлэх ёстой ба эдгээр нь $x_{i}$ зангилаанд агуулагдсан $s$ модны зангилаануудын дугааруудыг илэрхийлэх ба дурын дарааллаар хэвлэнэ.

Тэгээд $m - 1$ мөр хэвлэх ба мөр бүрт хоёр бүхэл тоо $p_{i}, q_{i}$ $(1 ≤ p_{i}, q_{i} ≤ m; p_{i} ≠ q_{i})$ байна. $p_{i}, q_{i}$ бүхэл тоон хослол нь Т-задралын $x_{p_{i}}$ ба $x_{q_{i}}$ зангилаануудын хооронд ирмэг буйг илтгэнэ.

Хэвлэсэн Т-задрал нь өгөгдсөн $s$ модны хувьд хамгийн тохиромжтой Т-задрал байх ёстой ба бүх тохиромжтой Т-задралуудын дундаас боломжит хамгийн цөөн тооны зангилаатай байх ёстой. Хэрвээ хамгийн цөөн тооны зангилаатай тохиромжтой олон Т-задрал байвал алийг нь ч хэвлэж болно.

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

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

Оролт
2
1 2
Гаралт
1
2 1 2
Оролт
3
1 2
2 3
Гаралт
2
2 1 2
2 2 3
1 2
Оролт
4
2 1
3 1
4 1
Гаралт
3
2 2 1
2 3 1
2 4 1
1 2
2 3
Сэтгэгдлүүдийг ачааллаж байна...