Тойрон аялал II

2s

512MB

1311

0%

Graph Algorithms

Байтеландад $n$ хот, $m$ нислэгийн холбоос бий. Нэг хотоос эхлээд нэг ба түүнээс дээш өөр хотоор дамжин эхлэсэн хотдоо эргэж ирдэг тойрон аялал зохио. Чиглэл дэх дундын хот бүр хоорондоо ялгаатай байх ёстой.

https://cses.fi/problemset/task/1678

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

Эхний мөрөнд $n$ ба $m$ хоёр бүхэл тоо байна: хот болон нислэгийн тоо. Хотууд $1,2,\dots,n$ гэж дугаарлагдсан.

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

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

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

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

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

4
2 1 3 2

0.1 / 64 KiB

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