D. Аяганы илбэ

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

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

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

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

F компаний ажилчид өөрсдийгөө зугаацуулах олон аргатай. Өнөөдөр тэд хуванцар аяга болон шилэн бөмбөгөөр илбэ үзүүлдэг алдартай илбэчинг урьсан.

Гол цэг нь үзэгчийн анхаарлыг илбэдэх юм. Анх үзэгч шугаманд байрласан $n$ хуванцар аяганы урд зогсоно. Тэгээд илбэчин жижиг шилэн бөмбөгийг нэг аяганы доор байрлуулаад аягануудыг холино. Тэгээд үзэгч шилэн бөмбөгийг нуусан аягыг таах ёстой.

F компаний ахлах кодчилогчийг хуурах тийм ч амар биш. Тэр гүйцэтгэлийг хараад хэд хэдэн чухал зүйлсийг анзаарсан:

  • аяга бүр тэмдэгтэй ба $1$-c $n$ хүртэл дугаарлагдсан ба бүх тэмдэг ялгаатай;
  • илбэчин аягануудыг $m$ үйлдэлд холих ба үйлдэл бүр дараах байдалтай байна: мөрийн $y_{i}$ байрлалд (байрлалууд зүүнээс баруун тийш 1-с эхлэн дугаарлагдана) байгаа $x_{i}$ тэмдэгтэй аягыг авна, тэгээд үүнийгээ аягатай мөрийн хамгийн эхэнд байрлуулна (эхний байрлалд).

Ахлах кодчилогч ажлаа тараад гэртээ ирсэн ба илбийг дахин хийхийг хүссэн. Харамсалтай нь тэр аягануудын анхны болон эцсийн байрлалыг санахгүй байна. Тэр зөвхөн илбэчиний хийсэн үйлдлүүдийг л санаж байна. Кодчилогчид туслана уу: үйлдлүүд хийгдсэн дарааллаараа өгөгдсөн бол тодорхойлогдсон үйлдлүүд өгөгдсөн дарааллаар хийгдсэн байж болох ядаж нэг анхны аягануудын дарааллыг ол. Бусад тохиолдолд ийм дараалал оршин байхгүй гэдгийг батал.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$ ба $m$ $(1 ≤ n, m ≤ 10^{6})$ байна. Дараагийн $m$ мөр бүрт хос бүхэл тоо байна. $i$-р мөрөнд $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n)$ бүхэл тоонууд байх ба илбэчиний $i$-р үйлдлийн тайлбар байна. Үйлдлүүд илбэчиний хийсэн дарааллаар өгөгдөх ба кодчилогч ч мөн адил энэ дарааллаар хийхийг хүсч байна.

Гаралт

Хэрвээ тодорхойлсон дараалал оршин байхгүй бол (програмчлагч үйлдлүүдийг буруу санасан) -1-г хэвлэ. Бусад тохиолдолд ялгаатай $n$ бүхэл тоог хэвлэх ба тус бүр нь $1$-c $n$ хүртэлх тоо байна. $i$-р тоо нь анх $i$-р байрлалд байсан аяганы тэмдэгийг илэрхийлнэ.

Хэрвээ хэд хэдэн зөв хариулт байвал та тоон дарааллын хувьд хамгийн бага нэгийг нь хэвлэх ёстой.

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

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

Оролт
2 1
2 1
Гаралт
2 1 
Оролт
3 2
1 2
1 1
Гаралт
2 1 3 
Оролт
3 3
1 3
2 3
1 3
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...