Cup Trick

题意翻译

给定一个长度为 $N$ 的排列和 $m$ 个操作。 每个操作都可以将一个位置在 $y_i$ 的数 $x_i$ 挪动到数列的开头。 现在只知道排列的长度 $N$ 和依次进行的 $m$ 个操作，要求找的可以按**所给顺序**进行操作的原排列。 如果有多个解，输出字典序最小的；如果无解，输出 `-1` 。

题目描述

The employees of the F company have lots of ways to entertain themselves. Today they invited a famous magician who shows a trick with plastic cups and a marble. The point is to trick the spectator's attention. Initially, the spectator stands in front of a line of $ n $ plastic cups. Then the magician places a small marble under one cup and shuffles the cups. Then the spectator should guess which cup hides the marble. But the head coder of the F company isn't easy to trick. When he saw the performance, he noticed several important facts: - each cup contains a mark — a number from $ 1 $ to $ n $ ; all marks on the cups are distinct; - the magician shuffles the cups in $ m $ operations, each operation looks like that: take a cup marked $ x_{i} $ , sitting at position $ y_{i} $ in the row of cups (the positions are numbered from left to right, starting from 1) and shift it to the very beginning of the cup row (on the first position). When the head coder came home after work he wanted to re-do the trick. Unfortunately, he didn't remember the starting or the final position of the cups. He only remembered which operations the magician performed. Help the coder: given the operations in the order they were made find at least one initial permutation of the cups that can go through the described operations in the given order. Otherwise, state that such permutation doesn't exist.

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ $ (1<=n,m<=10^{6}) $ . Each of the next $ m $ lines contains a couple of integers. The $ i $ -th line contains integers $ x_{i} $ , $ y_{i} $ $ (1<=x_{i},y_{i}<=n) $ — the description of the $ i $ -th operation of the magician. Note that the operations are given in the order in which the magician made them and the coder wants to make them in the same order.

输出格式

If the described permutation doesn't exist (the programmer remembered wrong operations), print -1. Otherwise, print $ n $ distinct integers, each from $ 1 $ to $ n $ : the $ i $ -th number should represent the mark on the cup that initially is in the row in position $ i $ . If there are multiple correct answers, you should print the lexicographically minimum one.

输入输出样例

输入样例 #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