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

2s

512MB

1311

0%

Graph Algorithms

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

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

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

Эхний мөрөнд $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

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