405738: GYM102058 A Dumae

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Dumaetime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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 Li-th, (Li + 1)-th, ..., (Ri - 1)-th, or Ri-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 vi can see student ui in the waiting line. It means student ui is relatively in front of student vi.

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.

Input

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 Li, Ri are given. (1 ≤ Li ≤ Ri ≤ N)

In the next M lines, two space-separated integers ui, vi are given. (1 ≤ ui ≤ N, 1 ≤ vi ≤ N, ui ≠ vi)

Output

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.

ExamplesInput
3 3
1 3
1 3
1 3
1 2
2 3
3 1
Output
-1
Input
3 3
1 3
1 3
1 3
1 2
2 3
1 3
Output
1
2
3

加入题单

上一题 下一题 算法标签: