← 返回题目列表

Codeforces · 420/D

D. 杯子魔术

中文机器翻译题面 查看原题

F公司的员工自娱自乐的方式有很多。今天他们请来了一位著名的魔术师,他用塑料杯和弹珠表演了魔术。

重点是要欺骗观众的注意力。最初,观众站在一排 n 个塑料杯前。然后魔术师将一颗小弹珠放在一个杯子下面,并搅动杯子。然后观众应该猜测哪个杯子里藏着弹珠。

不过F公司的编码长可不是那么好骗的。当他看到表演时,他注意到几个重要的事实:

- 每个杯子都包含一个标记 - 一个从 1 到 n 的数字;杯子上的所有标记都清晰可见;
- 魔术师将杯子进行 m 次洗牌,每次操作如下:拿一个标记为 xi 的杯子,坐在杯子排中的位置 yi 上(位置从左到右编号,从 1 开始),并将其移动到杯子排的最开头(第一个位置)。

当首席编码员下班回家时,他想重做这个技巧。不幸的是,他不记得杯子的起始位置或最终位置。他只记得魔法师做了哪些操作。帮助编码员:给定按其执行顺序进行的操作,找到至少一种可以按给定顺序执行所描述操作的杯子的初始排列。否则,说明这种排列不存在。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 106)。接下来的 m 行中的每一行都包含几个整数。第 i 行包含整数 xi, yi (1 ≤ xi, yi ≤ n) — 魔术师第 i 个操作的描述。请注意,这些操作是按照魔术师进行操作的顺序给出的,并且编码器希望按照相同的顺序进行操作。

输出

如果所描述的排列不存在(程序员记住了错误的操作),则打印-1。否则,打印 n 个不同的整数,每个整数从 1 到 n:第 i 个数字应代表杯子上最初位于第 i 行的标记。

如果有多个正确答案,则应打印字典顺序最小的一个。

示例

输入 #1

2 1
2 1

输出 #1

2 1

输入 #2

3 2
1 2
1 1

输出 #2

2 1 3

输入 #3

3 3
1 3
2 3
1 3

输出 #3

-1