19077번 - A Place For My Head 스페셜 저지다국어

문제

Artem has constructed a permutation $p$ of $n$ integers from 1ドル$ to $n$ during the last Jinotega beer party. Kostya tried to guess it, but had no success. Then Artem gave some hints to Kostya: for each $i = 1, \ldots, n,ドル he told him two integers $l_i \le r_i,ドル meaning that element $i$ is situated between positions $l_i$ and $r_i$ inclusively. Kostya is sure that the lexicographically smallest permutation satisfying these conditions is the one Artem has constructed. As it is too late, and Kostya's brain is not working as well as usually after several glasses of beer, you need to help him.

입력

The first line of input contains a positive integer $n$ (1ドル \le n \le 2 \cdot 10^5$), the length of the permutation.

Each of the next $n$ lines contain two integers $l_i$ and $r_i$ (1ドル \le l_i \le r_i \le n$).

출력

If it is impossible to reconstruct the permutation, print a line containing the integer $-1$.

Otherwise, print a line containing $n$ space-separated integers $p_1, p_2, \ldots, p_n$: the desired permutation.

제한

힌트