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

2s

512MB

1483

0%

Graph Algorithms

Каалеппи банк дээрэмдэж дууслаад одоо боомж руу явж байна. Цагдаа хотын зарим гудамжийг хааж түүнийг зогсоохыг хүсэж байна.

Банк ба боомжийн хооронд ямар ч чиглэл байха больгохын тулд хамгийн багадаа хэдэн гудамж хаах вэ?

Эх сурвалж: cses.fi

Оролтын формат

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

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

Гаралтын формат

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

Хязгаарлалт

$2 \le n \le 500$
$1 \le m \le 1000$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

2
3 4
1 4

0.1 / 64 KiB

Редактор уншиж байна...