405754: GYM102059 D Dumae

Do you know Dumae? It is a nickname of the most famous restaurant nearby KAIST, Dumae Charcoal-grilled Barbecue. Because 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 ) 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 ≤ N ≤ 300 000, 0 ≤ M ≤ 1 000 000)

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

In the next M lines, two space-separated integers u_i, v_i are given. (1 ≤ u_i ≤ N, 1 ≤ v_i ≤ N, u_i ≠ 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