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