Циклгүй, холбогдсон, чиглэлт бус графыг мод гэнэ. Мод нь зөвхөн хүмүүсийн төдийгүй шоргоолжнуудын ч сонирхлыг татдаг графын төрөл юм.

Нэгэн шоргоолж модны үндэс дээр зогсож байлаа. Уг модонд $n$ орой байдаг бөгөөд эдгээр нь $n-1$ мөчрөөр холбогдсон тул аль ч $2$ оройнуудын хооронд ямар нэгэн зам байдаг болохыг шоргоолж ажиглажээ. Ганцхан оройтой холбогдсон байдаг үндэснээс бусад оройг навч гэнэ.

Шоргоолж модны бүх оройгоор зочлоод, үндэс рүү буцаж, мөчир бүрийг 2 удаа дайран гарахыг хүсчээ. Мөн тэр тусгай дарааллаар навчнуудаар зочлохыг хүссэн байна. Та шоргоолжинд зориулж боломжит маршрутыг олж өгнө үү.

Оролт

Эхний мөр нь модны оройн тоог харуулах $n$ ($3≤n≤300$) тоог агуулна. Дараагийн $n-1$ мөрүүд нь мөчрүүдийг тодорхойлно. Мөчир бүрийг холбож буй $2$ оройн дугаар бүхий $2$ бүхэл тоогоор тодорхойлно. Мөчир бүр аль ч чиглэл рүү чиглүүлж болно. Оройнуудыг $1$-ээс эхлэн дугаарлана. Модны үндэс $1$ дугаартай. Сүүлийн мөр нь $k$ ширхэг бүхэл тоог агуулна. $k$ нь модон дахь навчнуудын тоо юм. Эдгээр тоонууд нь зочлох шаардлагатай навчнуудын дарааллыг илэрхийлнэ. Уг дараалалд навч бүр зөвхөн нэг удаа өгөгдөнө.

Гаралт

Хэрвээ боломжит маршрут байхгүй бол "-1" гэж хэвлээрэй. Эс бөгөөс маршрутыг тодорхойлох $2n-1$ ширхэг тоог буюу шоргоолжны очих орой бүрийн дугаарыг хэвлэнэ үү.