G. Галактик-ын нэгдэл

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

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

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

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

Нэгэн холын галактикт $1$-ээс $n$ хүртэл дугаарлагдсан хүмүүс амьдардаг $n$ ширхэг гариг байжээ. Нэгэн өдөр бүх $n$ ширхэг гаригийн ерөнхийлөгч хэнтэй ч хамааралгүйгээр нэгэн Нэгдсэн Галактик үүсгэн байгуулах нэгэн гайхалтай санаа олжээ. Одоо тэд өөрийн уг гайхалтай санаагаа өөрсдийн галактикийн хамтрагчдаа хүргэх хэрэгтэй байгаа бөгөөд ийм учраас ерөнхийлөгч болгон бусад ерөнхийлөгч нартайгаа тохиролцох тал дээр ихээхэн завгүй ажиллаж байгаа юм.

Ямар нэгэн хос гаригуудын хоорондох тохиролцоонд зориулан тэдгээрийн хооронд 2 урсгалтай харилцааны суваг оршин байх бөгөөд эдгээр суваг тус бүр нь дуудлагын хугацаа болох $t_{i}$-аар тодорхойлогдох юм. Тохиролцоо нь хэдэн цагийн турш болдог ба маш удаан хугацааны турш үргэлжилдэг байв. Нийт уг галактик нь $n$ ширхэг харилцааны сувагтай бөгөөд эдгээр нь бүх гаригуудыг нэгтгэн нэгэн сүлжээг үүсгэх ажээ. Өөрөөр хэлбэл ямар ч $v$ гаригаас ямар ч $u$ гариг уруу залгах боломжтой бөгөөд ингэхдээ $v_{1}$, $v_{2}$, ..., $v_{m}$ гэсэн завсрын гаригуудыг ашиглах юм. Тодруулбал бид $u$ болон $v_{1}$, $v_{1}$ болон $v_{2}$, ..., $v_{m - 1}$ болон $v_{m}$, $v_{m}$ болон $v$-ын хооронд байх сувгуудыг ашиглан эдгээр гаригуудыг холбох юм. $u$-аас $v$ гариг хүртэлх дуудлагын хугацаа нь эдгээр ашигласан сувгуудын дуудлагын хугацаануудын нийлбэртэй тэнцүү байна.

Иймд ерөнхийлөгч тус бүр нь бусад $n - 1$ ширхэг гаригуудын бүх ерөнхийлөгч нартай нэг нэгээр нь ярилцах хэрэгтэй болжээ. Эдгээр тохиролцоонуудыг заавал дараалсан байдлаар хийх ёстой ба ямар нэгэн гаригтай хийж буй тохиролцоо дуусах хүртэл өөр гариг уруу хийх дуудлагыг эхлүүлэхгүй байх юм. Уг ажил нь яаралтай ажил учраас хэрэгтэй гариг уруу залгах олон янзын ялгаатай аргууд дундаас бид хамгийн богино хугацаанд ярих аргыг нь сонгоно. Галактик-ын нэгдэл нь хэр чухал болохыг өөр гаригийн ерөнхийлөгчид батлан тайлбарлахад маш бага хугацаа шаардагдах бөгөөд ийм учраас эдгээр гариг бүртэй хийх тохиролцоонуудын үргэлжлэх хугацааг эдгээр гаригуудын хооронд хийх дуудлагын хугацаатай тэнцүү гэж үзэж болох юм. Ерөнхийлөгчид нь бусдынхаа төлөвлөгөөний талаар юу ч мэдэхгүй байгаа учраас тэд өөрсдийн хайж буй ерөнхийлөгч нь өөр уруу нь залгах эсвэл галактикийн нэгдлийн талаар өөр эх сурвалжаас мэдсэн байх боломжийн талаар огт тооцож үзэхгүй.

Бүх $n$ ширхэг гаригуудын нэгдсэн засгийн газар таныг эдгээр тохиролцооны төлөвлөгөөнүүдийг хэрэгжүүлж өгөхийг хүсжээ. Эхлээд та ерөнхийлөгч бүрийн хувьд түүний төлөвлөсөн тохиролцоонууд нь хэр удаан хугацааны туршид үргэлжлэхийг олж өгөх юм.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($3 ≤ n ≤ 200000$) өгөгдөх ба энэ нь Галактик-т байх гаригуудын тоог илэрхийлэх бөгөөд харилцааны сувгуудын тоо нь мөн уг тоотой тэнцүү байна. Дараагийн $n$ ширхэг мөрийн мөр болгонд 3-н бүхэл тоо $a_{i}$, $b_{i}$ болон $t_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 1 ≤ t_{i} ≤ 10^{3}$) өгөгдөх ба эдгээр нь уг харилцааны сувгаар холбогдож буй гаригуудын дугаар болон дуудлагын хугацааг илэрхийлнэ. Ямар нэгэн хос гаригуудын хооронд нэгээс олон тооны харилцааны суваг байхгүй байна.

Гаралт

Гаралтын эхний мөрөнд $n$ ширхэг бүхэл тоонууд хэвлэх бөгөөд эдгээр нь ерөнхийлөгч тус бүрийн төлөвлөсөн тохиролцоонуудынх нь үргэлжлэх хугацаануудыг илэрхийлнэ. Мөн эдгээр тоонуудыг зайгаар тусгаарлан хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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