Dumae

Dumae를 알고 있는가? KAIST 근처에서 가장 유명한 식당인 Dumae 숯불 바비큐다. 아직 문을 열지 않았는데도 많은 KAIST 학생이 줄을 선다. 학생들은 기다리는 시간이 얼마나 될지 궁금해서 자신의 순서를 추측하기 시작했다.

대기 줄에는 $N$명의 학생이 서 있으며, 각 학생은 $1$부터 $N$까지 서로 다른 학번을 가진다. 학번이 $i$인 학생은 자신이 줄의 $L_i$번째, $(L_i+1)$번째, $\cdots$, $(R_i-1)$번째, 또는 $R_i$번째 사람이라고 추측했다. 즉 학생 $i$의 앞에 서 있는 사람의 수는 구간 $[L_i-1, R_i-1]$에 속한다.

또한 $M$개의 주장이 있다. $i$번째 주장은 학생 $v_i$가 줄에서 학생 $u_i$를 볼 수 있다는 것이다. 이는 학생 $u_i$가 학생 $v_i$보다 앞에 서 있다는 뜻이다.

모든 추측과 주장을 만족하는 줄의 순서를 구하거나, 그런 순서가 없다고 보고하라.

첫 줄에 두 정수 $N$, $M$이 주어진다 ($1 ≤ N ≤ 300,000$, $0 ≤ M ≤ 1,000,000$).

다음 $N$개의 줄에 두 정수 $L_i$, $R_i$가 주어진다 ($1 ≤ L_i ≤ R_i ≤ N$).

다음 $M$개의 줄에 두 정수 $u_i$, $v_i$가 주어진다 ($1 ≤ u_i ≤ N$, $1 ≤ v_i ≤ N$, $u_i ≠ v_i$).

조건을 만족하는 순서가 없으면 $-1$을 출력한다. 그렇지 않으면 $N$개의 줄에 걸쳐 $i$번째 줄에 앞에서 $i$번째 학생의 학번을 출력한다.