H. Шинэ Жил ба Мартагдсан Мод

хугацааны хязгаарлалт 7 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Мод нь $n - 1$ ирмэгтэй холбогдсон чиглэлгүй граф байх ба $n$ нь оройнуудын тоог заана. Оройнууд нь $1$-c $n$ хүртэл дугаарлагдсан.

Бяцхан Лимак бол цагаан баавгай. Түүний баавгайн гэр бүл жил бүр Шинэ Жилийн мод засдаг. Нэг жилийн өмнө тэдний мод байнга засдагаас илүү сэтгэл хөдөлгөм байсан. Тиймээс тэд дараа жил адилхан мод засахаар шийдсэн. Лимак уг модыг санах үүрэг хүлээсэн.

Модыг бүхэлд нь цээжлэх нь хэцүү байсан. Лимак үүнийг тэмдэглэлийн дэвтэртээ тодорхойлж бичихээр шийдсэн. Тэр үзэг аваад мөр бүр нь ирмэгээр холбогдсон хоёр оройн индексийг агуулсан $n - 1$ мөр бичсэн.

Одоо Шинэ Жил хаяанд ирж Лимак нөгөө модыг дахин барих болсон. Мэдээж асуудал үүссэн. Учир нь жилийн өмнө тэр үнэхээр жаахан баавгай байсан ба тэр тоо болон үсэг мэддэггүй байсан, тэгээд тэр цифр бүрийг өөрийн мэдэх ганц тэмдэгт болох асуултын тэмдгээр орлуулсан. Энэ нь түүний дэвтэр дээр байгаа ямар ч оройн индексийн хувьд тэр зөвхөн үүнд байгаа цифрүүдийн тоог л мэднэ гэсэн үг. Тэр эдгээр тоонууд нь тэгээр эхлээгүй байсныг мэдэж байна.

Лимак гэрийнхнийгээ гонсойлгохыг хүсэхгүй байна. Түүний тэмдэглэлийг аваад Шинэ Жилийн модыг дахин засч өгнө үү. Лимакын бичлэгүүдтэй таарах дурын модыг олоод ирмэгүүдийг нь дурын дарааллаар хэвлэнэ үү. Лимак алдаа гаргасан байж болох ба таарах мод олдохгүй байвал "$-1$"-г (хашилтгүйгээр) хэвлэнэ үү.

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($2 ≤ n ≤ 200 000$) байх ба оройнуудын тоо.

Дараагийн $n - 1$ мөр бүрт зайгаар тусгаарлагдсан хоёр хоосон биш тэмдэгт мөр байх ба хоёулаа зөвхөн асуултын тэмдгээс тогтоно. Ямар ч тэмдэгт мөр $n$-н цифрийн тооноос их тэмдэгттэй байхгүй.

Гаралт

Хэрвээ Лимакийн бичлэгүүдтэй таарах мод олдохгүй бол "$-1$"-г (хашилтгүйгээр) нэг мөрөнд хэвлэнэ үү.

Бусад тохиолдолд Лимакын тэмдэглэлүүдтэй таарах дурын модыг тодорхойл. $n - 1$ мөрийн мөр бүрт зайгаар тусаарлагдсан хоёр бүхэл тоон утга байх ба ирмэгээр холбогдсон оройнуудын индексүүд байна. Та ирмэгүүдийг дурын дарааллаар хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
12
? ?
? ?
? ?
? ??
?? ?
?? ??
? ??
? ?
? ?
? ?
? ?
Гаралт
3 1
1 6
9 1
2 10
1 7
8 1
1 4
1 10
5 1
10 11
12 1
Оролт
12
?? ??
? ?
? ?
? ??
?? ?
?? ??
? ??
? ?
? ?
?? ??
? ?
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...