E. Бүтээгчид дахин тоголлоо

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

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

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

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

Шамбамбукли болон Мазукта бүтээгчид нь энгийн хүмүүсийн тоглохыг харах дуртай. Өнөөдөр тэд 2 хүн дараах тоглоомыг тоглохыг харжээ.

$n$ зангилаатай үндэстэй мод байна. Эдгээр $n$ ширхэг зангилааны $m$ ширхэг нь навч (навч нь хүүхэдгүй зангилааг хэлнэ). Модны мөчир болгон нь эцгээс хүүхэд уруу шууд холбодог. Модны навчис бүрийг $1$-ээс $m$ хүртэл дугаараар дугаарлана.

Анх үндэс дээр шатрын хүү байрлана. 2 тоглогч шатрын хүүг ээлжлэн хөдөлгөх бөгөөд хөдөлгөхдөө зангилааны хүүхэд уруу л хөдөлгөх боломжтой. Хэрвээ шатрын хүү хөдлөх боломжгүй болвол тоглоом шууд дуусна. Тоглоомын үр дүн нь шатрын хүүгийн хамгийн сүүлийн байрлал буюу навчны дугаар юм. Эхний нүүдлийг хийсэн хүн тоглоомын үр дүнг хамгийн их байлгах гэж хичээнэ. Харин 2 дахь тоглогч эсрэгээрээ үр дүнг хамгийн бага байлгахыг хичээнэ. 2 тоглогч нь байж болох хамгийн сайн хувилбараар нүүдэг.

Бүтээгчид нь бүхнийг чадагчид бөгөөд тоглоом эхлэхээс өмнө навчисан дээрх дугааруудыг дураараа өөрчилж чадна. Шамбамбукли нь тоглоомын үр дүнг хамгийн их байхаар дугааруудыг өөрчлөхийг хүсэж байгаа. Харин Мазукта тоглоомын үр дүнг хамгийн бага байхаар дугааруудыг өөрчлөхийг хүсэж байгаа. Хэрвээ Шамбамбукли дугааруудыг өөрчилвөл тоглоомын үр дүн хэд байх вэ? Харин Мазукта дугааруудыг өөрчилвөл тоглоомын үр дүн хэд байх вэ? Мэдээж бүтээгчид дугааруудыг өөрчлөхдөө хамгийн сайн боломжит хувилбарыг сонгоно. Энд тоглогчид алдалгүй нүүдэг гэдгийг анхаарна уу.

Оролт

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

Дараагийн $n-1$ ширхэг мөр болгонд мөчирны 2 төгсгөл болох 2 бүхэл тоонууд $u_{i}$, $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) өгөгдөнө. Энд мөчир нь зангилаа $u_{i}$-ээс эхлэн зангилаа $v_{i}$ дээр төгсөнө. Өөрөөр хэлвэл зангилаа $u_{i}$ нь эцэг, зангилаа $v_{i}$ нь түүний хүүхэд гэсэн үг. Энд өгөгдөх дүрс нь үндэстэй мод бөгөөд үндэс нь зангилаа $1$ гэдэг нь баталгаатай.

Гаралт

Тоглоомын гарж болох хамгийн их болон хамгийн бага утга болох зайгаар тусгаарлагдсан 2 бүхэл тоог хэвлэнэ үү.

Орчуулсан: Энхлут

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

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

Тэмдэглэл

Эхний жишээнд: мод 3-н ширхэг навчтай: 3, 4, 5. Хэрвээ хамгийн их дугаар 3-ыг зангилаа 3 дээр байрлуулвал эхний тоглогч нүүн тоглоомын үр дүн 3 болох болно. Эсрэгээрээ, ямар ч өөрчлөлт хийсэн эхний тоглогч дор хаяж 2 гэсэн дугаар авж чадахыг төвөггүй харж болно.

2 дахь жишээнд: ямар ч өөрчлөлт хийсэн эхний тоглогч 3 дугаартай навч уруу очих нүүдэл хийж чадна.

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