Цагдаагийн хөөн мөрдөлт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$: уулзварууд болон гудамжуудын тоо. Уулзварууд $1,2,\dots,n$ гэж дугаарлагдсан. Банк $1$-р уулзварт, боомж $n$-р уулзварт байна.

Үүний дараа гудамжуудыг тодорхойлсон $m$ мөр байна. Мөр бүрд хоёр бүхэл тоо $a$ ба $b$: $a$ ба $b$ уулзваруудын хооронд гудамж байна. Бүх гудамж хоёр чиглэлтэй бөгөөд хоёр уулзварын хооронд хамгийн ихдээ нэг гудамж байна.

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