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
Сэтгэгдлүүдийг ачааллаж байна...