B. Баавгай ба 2 маршрут

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

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

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

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

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

Лимак баавгай нэгэн удаа $a$ хотод байсан бөгөөд $b$ хот уруу явахыг хүсжээ. Уг хотуудыг холбосон шууд зам байгаагүй учраас тэрээр маш урт хугацааны аялал хийхээр болсон ба ингэхдээ хот болгоныг яг нэг удаа дайрч гарсан байх юм. Илүү тодруулбал:

  • $a$ болон $b$-ын хооронд ямар ч зам байхгүй байна.
  • $v_{1} = a$, $v_{n} = b$ байх бөгөөд бүрийн хувьд $v_{i}$ болон $v_{i + 1}$-ын хооронд ямар нэгэн зам оршин байх $n$ ширхэг ялгаатай хотуудын дараалал (маршрут) $v_{1}, v_{2}, ..., v_{n}$ оршин байх юм.

Өөр нэгэн өдөр мөн төстэй зүйл тохиолджээ. Лимак $c$ хот болон $d$ хотуудын хооронд аялахыг хүссэн ба эдгээр хотуудыг хооронд нь шууд холбох ямар нэгэн зам байсангүй. Гэхдээ $u_{1} = c$, $u_{n} = d$ байх бөгөөд бүрийн хувьд $u_{i}$ болон $u_{i + 1}$-ын хооронд ямар нэгэн зам оршин байх $n$ ширхэг ялгаатай хотуудын дараалал (маршрут) $u_{1}, u_{2}, ..., u_{n}$ оршин байв.

Түүнчлэн Лимак Баавгайн нутагт хамгийн ихдээ $k$ ширхэг зам байна хэмээн бодож байв. Тэрээр өөрийн санаж буй бүх зүйл нь зөв эсэхийг мэдэхийг хүсжээ.

Та өгөгдсөн $n$, $k$ болон 4 ширхэг ялгаатай хотууд $a$, $b$, $c$, $d$-ын хувьд өгөгдсөн бүх нөхцөлүүдийг хангаж байхаар $(v_{1}, ..., v_{n})$ болон $(u_{1}, ..., u_{n})$ гэсэн боломжит маршрутуудыг олж чадах уу? Ямар нэгэн хариулт олно уу эсвэл хариулт олох боломжгүй бол -1 гэж хэвлэнэ үү.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($4 ≤ n ≤ 1000$, $n - 1 ≤ k ≤ 2n - 2$) өгөгдөх ба эдгээр нь харгалзан хотуудын тоо болон замуудын тооны боломжит хамгийн их утгыг тус тус илэрхийлнэ.

2-дахь мөрөнд 4 ширхэг ялгаатай бүхэл тоо $a$, $b$, $c$ болон $d$ ($1 ≤ a, b, c, d ≤ n$) өгөгдөнө.

Гаралт

Хэрэв өгөгдсөн бүх нөхцөлийг хангах боломжгүй байвал -1 гэж хэвлэнэ үү. Бусад тохиолдолд 2 мөрөнд маршрутуудын тайлбарыг хэвлэнэ үү. Эхний мөрөнд $n$ ширхэг ялгаатай бүхэл тоонууд $v_{1}, v_{2}, ..., v_{n}$-уудыг хэвлэх ёстой бөгөөд энд $v_{1} = a$, $v_{n} = b$ байх юм. 2-дахь мөрөнд $n$ ширхэг ялгаатай бүхэл тоонууд $u_{1}, u_{2}, ..., u_{n}$-уудыг хэвлэх ёстой ба энд $u_{1} = c$, $u_{n} = d$ байх юм.

2 маршрутууд нь нийтдээ хамгийн ихдээ $2n - 2$ ширхэг замууд үүсгэх юм: $(v_{1}, v_{2}), (v_{2}, v_{3}), ..., (v_{n - 1}, v_{n}), (u_{1}, u_{2}), (u_{2}, u_{3}), ..., (u_{n - 1}, u_{n})$. Хэрэв таны хариулт нь $k$-аас олон тооны ялгаатай замууд агуулах эсвэл өөр ямар нэгэн нөхцөлийг хангаагүй тохиолдолд таны хариултыг буруу гэж үзэх юм. $(x, y)$ болон $(y, x)$ гэдэг нь ижилхэн замууд болохыг анхаарна уу.

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

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

Оролт
7 11
2 4 7 3
Гаралт
2 7 1 3 6 5 4
7 1 5 4 6 2 3
Оролт
1000 999
10 20 30 40
Гаралт
-1

Тэмдэглэл

Эхний жишээнд нийтдээ $7$ ширхэг хот байх бөгөөд хамгийн ихдээ $11$ ширхэг зам оршин байж болох юм. Уг жишээний хариултыг зурж үзэхэд нийтдээ $10$ ширхэг зам үүсгэсэн байна. Мөн та $2$ ба $4$-р хотуудын хооронд болон $7$ ба $3$-р хотуудын хооронд $n$ урттай энгийн маршрут байгааг хялбархан харж болно.

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