5298: Stack
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
ZYT had a magic permutation a1,a2,⋯,ana_1,a_2,\cdots, a_na1,a2,⋯,an, and he constructed a sequence b1,b2,⋯bnb_1,b_2,\cdots b_nb1,b2,⋯bn by the following pseudo code:
Stk is an empty stack
for i = 1 to n :
while ( Stk is not empty ) and ( Stk's top > a[i] ) :
pop Stk
push a[i]
b[i]=Stk's size
But he somehow forgot the permutation a, and only got some k elements of bi.
Construct a permutation a satisfying these bi , or determine no such permutation exists.
Here a permutation refers to a sequence that contains all integers from 1 to n exactly once.
输入
he first line contains two integers n,k(1≤k≤n) the length of the permutation, the number of left bi.
Then k lines each contains two integer pi,xi, denoting that bpi=xi.
输出
Output one line with n integers a1,a2,⋯an— a possible permutation.
If no such permutation exists, output one integer -1.
样例输入 复制
5 2
2 2
5 4样例输出 复制
1 2 5 3 4提示
It's guaranteed that n≤106,1≤pi,xi≤n and ∀i≠j,pi≠pj.