CF420D Cup Trick

F 公司员工有很多自娱自乐的方法。今天他们请来一位著名的魔术师，带来一个用塑料杯和弹珠的魔术。 这个魔术的目的在于迷惑观众的注意力。最初，观众站在一排 $n$ 个塑料杯前。魔术师将一颗小弹珠放在其中一个杯子下，并将杯子们进行若干次洗牌。然后观众需要猜测哪一个杯子下面藏着弹珠。 但 F 公司的首席程序员并不容易被愚弄。当他看到表演时，他注意到几个重要的细节： - 每个杯子上都有一个编号，编号是从 $1$ 到 $n$ 的整数，所有杯子的编号都不同； - 魔术师通过 $m$ 次操作洗牌。每次操作形如：取出编号为 $x_{i}$、当前第 $y_{i}$ 个位置上的杯子（位置从左到右编号，起始为 $1$），然后把它移到杯子队列的最前端（即第一个位置）。 当这位程序员下班回家后，他想要重新还原当时的魔术。不幸的是，他已经记不清杯子的初始和最终排列，他只记得魔术师执行的这些操作。请你来帮助他：给定这些操作的顺序，找出至少一个能够执行这些操作的初始杯子排列。如果不存在这样的排列，请说明。

第一行包含两个整数 $n$ 和 $m$，满足 $1\leq n,m\leq 10^6$。 接下来的 $m$ 行，每行包含两个整数，第 $i$ 行为 $x_{i}$ 和 $y_{i}$，表示魔术师的第 $i$ 次操作。$1\leq x_{i},y_{i}\leq n$。注意，操作按实际执行顺序给出，程序员也想按同样的顺序执行这些操作。

如果不存在满足条件的排列（即程序员记错了操作），输出 $-1$。否则，输出 $n$ 个不同的整数，范围均为 $1$ 到 $n$，第 $i$ 个数表示初始时第 $i$ 个位置上的杯子的编号。 如果有多组答案，输出字典序最小的那一个。

由 ChatGPT 5 翻译