H. Аяллын хөтөч

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

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

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

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

Дурын хүнийг аялагчийн хөтчөөр сонгох нь тийм ч амар биш. Сайн аяллын хөтөч аялагчдын урсгалыг улс даяар сайтар тараах ёстой ба аяллаас олох орлогын урсгалыг хамгийн их байлгах хэрэгтэй. Эдгээр шалтгаануудын улмаас албан ёсны хөтөч болоход хэд хэдэн тооны нөхцөл тавьдаг ба Аялал жуулчлалын яамнаас баталгаажуулдаг.

Аялал жуулчлалын яамнаас улсын $n$ хотоос $k$ гайхалтай хотыг багтаасан жагсаалт гаргасан. Үндсэндээ дүрэм журмыг баримтлах мөн яаманд зөвшөөрөгдөхийн тулд аяллын хөтөч гайхалтай хотуудын хооронд явсан хэд хэдэн маршрут гаргах ёстой ба дараах нөхцөлүүдийг хангах ёстой:

  • маршрут бүрийн эхний болон сүүлийн хотууд нь ялгаатай гайхалтай хотууд байх;
  • гайхалтай хот бүр нэг л маршрутын төгсгөлийн цэг байж чадна;
  • ямар ч хоёр маршрут нэг замаар явахгүй.

Маршрут мөн гайхалтай хотоор дайрч болно. Аяллын орлого нь аяллын хөтчийн маршрутуудын тооноос ихээр хамаарах ба таны ажил бол хамгийн олон маршрут багтаасан аяллын хөтчийн дүрмүүдтэй нийцэх маршрутын бүрдлийг олох юм.

Оролт

Эхний мөрөнд гурван бүхэл тоо $n,  m,  k$ $(1 ≤ n ≤ 50000,  0 ≤ m ≤ 50000,  1 ≤ k ≤ n)$ байх ба харгалзан улсын хотуудын тоо, улсын нийт замын тоо ба гайхалтай хотуудын тоо юм.

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

Сүүлийн мөрөнд ялгаатай $k$ бүхэл тоо байх буюу гайхалтай хотуудын жагсаалт юм. Бүх хотууд $1$-c $n$ хүртэл дугаарлагдана.

Гаралт

Гаралтын эхний мөрөнд аяллын хөтчид байгаа маршрутын тоо $c$ байна. Дараагийн $c$ мөр бүрт нэг аяллын маршрут байна. Маршрут бүр "$t$ $v_{1}$ $v_{2}$ ... $v_{t + 1}$" хэлбэртэй бичигдэх ба энд $t$ нь маршрут дахь замуудын тоо бол $v_{1},  v_{2}, ..., v_{t + 1}$ тоонуудаар хотуудын дугаарыг маршрут дахь дарааллаар илэрхийлнэ.

Хэрвээ хэд хэдэн хариулт байвал алийг нь ч хэвлэж болно.

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

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

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