E. Үхлийн төгсгөл

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

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

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

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

Бертаун-дахь амьдрал хэцүү болж байв. Уг хот нь хэт олон замтай бөгөөд засгийн газар нь эдгээр замуудыг арчлахын тулд маш их хөрөнгө мөнгө зарцуулж байгаа. Хот нь нийт $n$ ширхэг замын уулзвар болон $m$ ширхэг 2 урсгалтай замтай ба ямар ч уулзвараас бусад ямар ч уулзвар уруу явж болдог байв. Хотын дарга үлдэх замын тоо нь $n - 1$ ширхэг байхаар хэсэг замыг хаахыг хүсэж байгаа бөгөөд ингэснээр ямар ч уулзвараас бусад ямар ч уулзвар уруу явж чаддаг хэвээр байх ёстой юм. Түүнчлэн хотын дарга үхлийн төгсгөлүүдийг бодолцож үзэх бөгөөд үхлийн төгсгөл гэдэг нь зөвхөн нэг зам тухайн уулзвараас гарч байх замын уулзваруудыг нэрлэдэг. Хэт их болон хэт бага уулзвар байж болохгүй юм. Иймээс асуудлыг хэлэлцэж үзээд хотын дарга болон түүний туслахууд хэсэг замыг хаасны дараа яг $k$ ширхэг үхлийн төгсгөл байх ёстой гэж шийджээ. Таны даалгавар бол дараах нөхцөлүүдийг хангаж байхаар хэсэг замуудыг хаах ялгаатай аргын тоог тоолох юм:

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

Хэрэв эхний арга дээр хаалттай, 2-р арга дээр нээлттэй байх зам оршин байвал уг 2 аргыг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд харгалзан уулзваруудын тоо, замуудын тоо болон үхлийн төгсгөлүүдийн тоог илэрхийлэх 3 бүхэл тоо $n$, $m$ болон $k$ ($3 ≤ n ≤ 10, n - 1 ≤ m ≤ n*(n - 1) / 2, 2 ≤ k ≤ n - 1$) өгөгдөнө. Дараагийн $m$ мөрийн мөр болгонд ялгаатай 2 бүхэл тоо $v_{1}$ болон $v_{2}$ ($1 ≤ v_{1}, v_{2} ≤ n, v_{1} ≠ v_{2}$) өгөгдөх ба эдгээр нь ямар нэгэн замаар холбогдсон уулзваруудын дугааруудыг илэрхийлнэ. Хос уулзвар бүрийн хувьд тэдгээрийн хооронд нэгээс олон зам байхгүй байна. Уулзварууд нь $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байна. Уулзвар болгоноос бусад ямар ч уулзвар уруу анхны замуудыг даган явсаар хүрэх боломжтой байна.

Гаралт

Шаардагдсан аргуудын тоог хэвлэнэ үү.

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

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

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