B. Дэлхийн аялал

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

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

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

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

Алдартай барималч Кикассо дэлхийг тойрон аялах гэж байна!

Мэдээж яг дэлхий даяар биш. Гэхдээ хүн бүрт уран барималчийн бүтээлүүдийг харах завшаан тохиох албагүй, тийм биш гэж үү? Өөр ямар нэгэн хязгаарлалт байхгүй. Кикассо тойрон аялалаа өөрийн уугуул нутаг Берланд даяар үргэлжлүүлнэ.

Кикассо өөрийн бүтээлдээ маш үнэнч ба боломжит хамгийн бага хэмжээгээр сатаарахыг хүсч байна. Тиймээс тэр зөвхөн дөрвөн хотоор л зочилно. Эдгээр хотууд ялгаатай ба ямар нь ч түүний дуртай хот биш байна. Мэдээж мөнгө хэмнэх үүднээс тэр эдгээр хотуудын хоорондох хамгийн богино замуудыг сонгосон. Гэхдээ таны анзаарсанчлан Кикассо бол хачин хүн. Мөн тэр үзэсгэлэн зохион байгуулах дургүй, тэр газар орноор явж байгалийн үзэсгэлэнг мэдрэх дуртай. Тэр аялах нийт зайгаа боломжит хамгийн их байлгахыг хүсч байна. Гэсэн ч уран барималч юм төлөвлөхдөө тааруу ба таны тусламжийг хүсч байна.

Берландад $n$ хот ба $m$ нэг чиглэлтэй зам байгаа. Та Кикассогийн аялах дөрвөн ялгаатай хотуудыг сонгох ёстой ба түүний аялах дарааллыг ч мөн тодорхойлно. Тэр таны дарааллын дагуу таны жагсаалтын хамгийн эхний хотоос эхэлж хамгийн сүүлийн хотод дуусахаар хос хот бүрийн хоорондох хамгийн богино замыг сонгон явах ба түүний аялах нийт зай хамгийн их байх ёстой.

Дундын маршрут аялалд сонгогдсон хотуудаар дайрч болох ба нэг хотоор хоёр удаа ч дайрч болно. Жишээлбэл аялал дараах байдалтай байж болно: . Зочлох дараалалд байгаа дөрвөн хот нь дээгүүрээ зураастай байна: $[1, 5, 2, 4]$.

Берланд бол өндөр хөгжилтэй орон. Тиймээс нанотехнологийг ашиглан бүх замыг ижил урттай болгож зассан. Зарим нэг шалтгаанаас болж энэ улсад энгийн машинаар явах нь түгээмэл биш ба нэгээс нь нөгөөд машинаар очих боломжгүй хос хотууд байж болно. Гэсэн ч Кикассо маш хуучинсаг үзэлтэй нэгэн ба зөвхөн машинаар л явдаг. Уран барималч маань зөвхөн машин ашиглаад аялаж болох хотуудыг сонго. Ийм сонголт хийх боломж үргэлж байх болно.

Оролт

Эхний мөрөнд хос бүхэл тоо $n$ ба $m$ ($4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000$) байх ба Берланд дахь хотуудын тоо болон нэг чиглэлт замуудын тоо юм.

Дараагийн $m$ мөр бүрт хос бүхэл тоо $u_{i}, v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) байх ба $u_{i}$-c $v_{i}$ хотруу чиглэсэн нэг чиглэлт замыг илэхийлнэ. $u_{i}$ ба $v_{i}$ нь ялгаатай байх албагүй. Мөн нэг хос хотуудын хооронд хэд хэдэн нэг чиглэлт замууд байж болно.

Гаралт

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

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

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

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

Тэмдэглэл

$x$ ба $y$ хотуудын хоорондох хамгийн богино замыг $d(x, y)$ гэе. Тэгвэл жишээн дээр $d(2, 1) = 3, d(1, 8) = 7, d(8, 7) = 3$ байна. Нийт зай нь $13$-тай тэнцүү.

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