P14624 [2018 KAIST RUN Fall] Dumae

你知道 **Dumae** 吗？这是 KAIST 附近最著名的餐厅 **Dumae 炭火烧烤** 的昵称。因为 **Dumae** 是一家非常著名的餐厅，所以很多 KAIST 学生在餐厅还没开门时就开始排队。学生们想知道他们需要等多久，于是开始猜测自己的排队顺序。 等待队列中有 $N$ 名学生，每名学生有一个从 $1$ 到 $N$ 的唯一学号。学生 $i$（学号为 $i$ 的学生）猜测他/她在队列中是第 $L_i$ 个、第 $(L_i+1)$ 个、……、第 $(R_i-1)$ 个或第 $R_i$ 个人。（即，排在他/她前面的人数在区间 $\left[L_{i} - 1, R_{i} - 1\right]$ 内）此外，还有 $M$ 条声称，其中第 $i$ 条声称学生 $v_i$ 可以在等待队列中看到学生 $u_i$。这意味着学生 $u_i$ 排在学生 $v_i$ 的前面。 你想知道是否所有学生的猜测和声称都是正确的。找到一个满足所有猜测和声称的排队顺序，或者报告这样的顺序不存在。

第一行包含两个以空格分隔的整数 $N, M$（$1 \leq N \leq 300,000$，$0 \leq M \leq 1,000,000$）。 接下来的 $N$ 行中，每行给出两个以空格分隔的整数 $L_i, R_i$（$1 \leq L_i \leq R_i \leq N$）。 接下来的 $M$ 行中，每行给出两个以空格分隔的整数 $u_i, v_i$（$1 \leq u_i \leq N$，$1 \leq v_i \leq N$，$u_i \neq v_i$）。

如果没有满足条件的答案，输出 $-1$。 否则，输出 $N$ 行。 在第 $i$ 行，输出从前面数第 $i$ 个学生的学号。

翻译由 DeepSeek V3 完成