Хамгийн урт нислэгийн чиглэл

2s

512MB

1329

0%

Graph Algorithms

Уолеви тэмцээнд ялж, шагнал нь хотуудаар дамжин нэг буюу хэд хэдэн нислэгээс бүрдэх үнэгүй аялал болов. Уолеви хамгийн олон хотод орох аяллыг сонгохыг хүсдэг.

Уолеви Сюрьялягаас Лехмяля руу хамгийн олон хотод орж нисэхийг хүсдэг. Боломжит нислэгүүдийн жагсаалт өгөгдсөн бөгөөд нислэгийн сүлжээнд чиглэлтэй цикл байхгүй.

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

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

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо: хот болон нислэгийн тоо. Хотууд $1,2,\dots,n$ -ээр дугаарлагдсан. $1$ дугаар хот Сюрьяля, $n$ дугаар хот Лехмяля.

Дараа нь $m$ мөрөнд нислэгүүд байна. Мөр бүрд $a$ , $b$ хоёр бүхэл тоо: $a$ хотоос $b$ хот руу нислэг бий. Нислэг бүр нэг чиглэлтэй.

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

Эхлээд чиглэл дээрх хотын хамгийн их тоог хэвлэ. Дараа нь хотуудыг зочлох дарааллаар нь хэвлэ. Ямар ч зөв шийдлийг хэвлэж болно.

Шийдэл байхгүй бол "IMPOSSIBLE" гэж хэвлэ.

Хязгаарлалт

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

4
1 3 4 5

0.1 / 64 KiB

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