E. Хамгийн богино зам

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

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

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

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

Эртний Бэрланд $n$ хоттой, ижил урттай, хоёр урсгалтай $m$ замтай байв. Хотууд $1$-ээс $n$ хүртэл дугаарлагдсан. Эртний мухар сүсгийн дагуу хэрвээ аялагч дунд нь өөр хотоор дайралгүй $a_i$, $b_i$, $c_i$ хотуудаар дараалан өнгөрвөл үнэхээр аймшигтай зүйл түүнийг хүлээж байдаг гэлцдэг.

Хотод нийт $k$ ширхэг ийм гурвал байдаг. Гурвал бүр яг дарааллаараа өгөгднө, энэ нь жишээлбэл та $a_i$, $c_i$, $b_i$ гэсэн дарааллаар аялах боломжтой. Вася $1$ хотоос $n$ хот руу тэр мухар сүсгийг зөрчилгүйгээр явахыг хүсэв. Түүний туулах хамгийн богино замын уртыг олно уу. Бас ямар маршрутаар явахыг нь зааж өгнө үү.

Оролт

Эхний мөр харгалзан хотын тоо, замын тоо, хориотой гурвалын тоо болох $n$, $m$, $k$ ($2 ≤ n ≤ 3000$, $1 ≤ m ≤ 20000$, $0 ≤ k ≤ 10^5$) гурван бүхэл тоог агуулна.

Дараагийн $m$ мөрөнд мөр бүрт замыг илэрхийлэх $x_i$, $y_i$ ($1 ≤ x_i, y_i ≤ n$) хоёр бүхэл тоог агуулна. Зам нь уг замаар холбогдсон хоёр хотоор тодорхойлогдно. Хот өөртэйгөө замаар холбогдохгүй ба хос хотын хооронд нэгээс олон зам байж болохгүй.

Дараагийн $k$ мөрөнд хориотой гурвалууд болох $a_i$, $b_i$, $c_i$ ($1 ≤ a_i, b_i, c_i ≤ n$) гурван бүхэл тоо өгөгднө. Гурвал бүр энэ жагсаалтад нэгээс олон удаа байхгүй. Гурвал дахь гурван хот хоорондоо ялгаатай.

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

Гаралт

$1$-ээс $n$ рүү явах зам байхгүй бол $-1$ гэж хэвлэ. Бусад тохиолдолд эхний мөрөнд $1$-ээс $n$ хот руу очих хамгийн богино замын урт болох $d$ тоог хэвлэнэ. Хоёрдахь мөрөнд Васягийн явах ямар нэгэн хамгийн богино замыг илэрхийлэх $d + 1$ ширхэг бүхэл тоог хэвлэ. Энэ зам $1$ хотоос эхлэн $n$ хот дээр төгсөх ёстой.

Орчуулсан: Sugardorj

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

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