Codeforces Round #804 (Div. 2)
3 өдрийн дараа |
D. Модон дээрх шоргоолж
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Циклгүй, холбогдсон, чиглэлт бус графыг мод гэнэ. Мод нь зөвхөн хүмүүсийн төдийгүй шоргоолжнуудын ч сонирхлыг татдаг графын төрөл юм.
Нэгэн шоргоолж модны үндэс дээр зогсож байлаа. Уг модонд $n$ орой байдаг бөгөөд эдгээр нь $n-1$ мөчрөөр холбогдсон тул аль ч $2$ оройнуудын хооронд ямар нэгэн зам байдаг болохыг шоргоолж ажиглажээ. Ганцхан оройтой холбогдсон байдаг үндэснээс бусад оройг навч гэнэ.
Шоргоолж модны бүх оройгоор зочлоод, үндэс рүү буцаж, мөчир бүрийг 2 удаа дайран гарахыг хүсчээ. Мөн тэр тусгай дарааллаар навчнуудаар зочлохыг хүссэн байна. Та шоргоолжинд зориулж боломжит маршрутыг олж өгнө үү.
Оролт
Эхний мөр нь модны оройн тоог харуулах $n$ ($3≤n≤300$) тоог агуулна. Дараагийн $n-1$ мөрүүд нь мөчрүүдийг тодорхойлно. Мөчир бүрийг холбож буй $2$ оройн дугаар бүхий $2$ бүхэл тоогоор тодорхойлно. Мөчир бүр аль ч чиглэл рүү чиглүүлж болно. Оройнуудыг $1$-ээс эхлэн дугаарлана. Модны үндэс $1$ дугаартай. Сүүлийн мөр нь $k$ ширхэг бүхэл тоог агуулна. $k$ нь модон дахь навчнуудын тоо юм. Эдгээр тоонууд нь зочлох шаардлагатай навчнуудын дарааллыг илэрхийлнэ. Уг дараалалд навч бүр зөвхөн нэг удаа өгөгдөнө.
Гаралт
Хэрвээ боломжит маршрут байхгүй бол "-1" гэж хэвлээрэй. Эс бөгөөс маршрутыг тодорхойлох $2n-1$ ширхэг тоог буюу шоргоолжны очих орой бүрийн дугаарыг хэвлэнэ үү.
Орчуулсан: Солонго
Жишээ тэстүүд
Оролт
3 1 2 2 3 3
Гаралт
1 2 3 2 1
Оролт
6 1 2 1 3 2 4 4 5 4 6 5 6 3
Гаралт
1 2 4 5 4 6 4 2 1 3 1
Оролт
6 1 2 1 3 2 4 4 5 4 6 5 3 6
Гаралт
-1