Trò Xếp Cốc

Điểm: 8,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một nhà ảo thuật biểu diễn trò xếp cốc. Ban đầu có $n$ chiếc cốc đặt thành một hàng ngang. Mỗi cốc được đánh dấu bằng một số nguyên phân biệt trong khoảng từ $1$ đến $n$ — gọi số này là nhãn của cốc. Các vị trí trong hàng được đánh số từ $1$ (trái) đến $n$ (phải).

Nhà ảo thuật thực hiện $m$ thao tác. Thao tác thứ $i$ được mô tả bởi cặp $(x_{i}, y_{i})$ với ý nghĩa: vào thời điểm thực hiện thao tác này, chiếc cốc mang nhãn $x_{i}$ đang ở vị trí $y_{i}$ trong hàng. Sau đó, nhà ảo thuật lấy chiếc cốc đó ra và đặt lên vị trí $1$ (đầu hàng); các cốc đứng phía trước nó bị đẩy lùi sang phải $1$ đơn vị. Số lượng cốc trong hàng luôn giữ nguyên là $n$ trong suốt $m$ thao tác.

Bạn được cho thứ tự $m$ thao tác. Hãy khôi phục một hoán vị nhãn ban đầu của hàng cốc sao cho khi áp dụng đúng dãy thao tác này, mọi thao tác đều phù hợp với mô tả (tức là vào thời điểm thực hiện thao tác $i$ , cốc mang nhãn $x_{i}$ thật sự đang ở vị trí $y_{i}$ ). Nếu có nhiều hoán vị thỏa mãn, in ra hoán vị nhỏ nhất theo thứ tự từ điển. Nếu không tồn tại, in ra $- 1$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_{i}$ và $y_{i}$ — mô tả thao tác thứ $i$ .

Dữ liệu ra

Nếu không tồn tại hoán vị ban đầu thỏa mãn, in ra một dòng chứa $- 1$ .
Ngược lại, in ra $n$ số nguyên phân biệt — nhãn của các cốc theo thứ tự từ trái sang phải trong hoán vị ban đầu (lấy hoán vị nhỏ nhất theo thứ tự từ điển).

Ràng buộc

$1 \leq n, m \leq 10^{6}$
$1 \leq x_{i}, y_{i} \leq n$

Ví dụ

Input	Output	Giải thích
2 1 2 1	2 1	Hoán vị ban đầu $[2, 1]$ . Thao tác duy nhất: cốc nhãn $2$ ở vị trí $1$ — đúng.
3 2 1 2 1 1	2 1 3	Hoán vị ban đầu $[2, 1, 3]$ . Thao tác 1: cốc nhãn $1$ ở vị trí $2$ , đưa lên đầu → $[1, 2, 3]$ . Thao tác 2: cốc nhãn $1$ ở vị trí $1$ — đúng.
3 3 1 3 2 3 1 3	-1	Không có hoán vị ban đầu nào phù hợp với cả ba thao tác.

Bình luận

Không có bình luận tại thời điểm này.