Ялгаатай чиглэлүүд

2s

512MB

1500

0%

Graph Algorithms

Тоглоом нь $n$ өрөө, $m$ телепортоос бүрдэнэ. Өдөр бүрийн эхэнд та $1$ -р өрөөнөөс эхлээд $n$ -р өрөөнд хүрэх ёстой.

Тоглоомын туршид телепорт бүрийг хамгийн ихдээ нэг удаа ашиглаж болно. Чиглэлүүдээ ухаалгаар сонговол хэдэн өдөр тоглож чадах вэ?

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

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

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ : өрөөнүүд болон телепортуудын тоо. Өрөөнүүд $1,2,\dots,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

0.1 / 64 KiB

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