题目描述

Do you know $\textit{Dumae}$? It is a nickname of the most famous restaurant nearby KAIST, $\textit{Dumae Charcoal-grilled Barbecue}$. Because $\textit{Dumae}$ is a very famous restaurant, lots of KAIST students stand in line even though it has not opened yet. Students wonder how long they have to wait, so they started to guess their order.

There are $N$ students in waiting line and each of them has a distinct student ID from $1$ to $N$. Student $i$ (student with student ID $i$) guessed that he/she is either $L_i$-th, $(L_i+1)$-th, ..., $(R_i-1)$-th, or $R_i$-th person in the line. (i.e. the number of people standing relatively in front of him/her is in the interval $\left[L_{i} - 1, R_{i} - 1\right]$) Also, $M$ claims are made, of which the $i$-th says that student $v_i$ can see student $u_i$ in the waiting line. It means student $u_i$ is relatively in front of student $v_i$.

You wonder if all of students' guesses and claims were right. Find an order of waiting line that satisfies all the guesses and claims, or report that such an order does not exist.

输入格式

The first line contains two space-separated integers $N, M$. ($1 \leq N \leq 300\,000, 0 \leq M \leq 1\,000\,000$)

In the next $N$ lines, two space-separated integers $L_i, R_i$ are given. ($1 \leq L_i \leq R_i \leq N$)

In the next $M$ lines, two space-separated integers $u_i, v_i$ are given. ($1 \leq u_i \leq N$, $1 \leq v_i \leq N$, $u_i \neq v_i$)

输出格式

If there is no answer that satisfies the condition, print $-1$.

Otherwise, print $N$ lines. In the $i$-th line, print the student ID of the $i$-th student from the front.

3 3
1 3
1 3
1 3
1 2
2 3
3 1

-1

3 3
1 3
1 3
1 3
1 2
2 3
1 3

1
2
3