AT_pakencamp_2022_day1_i Forgotten Sequence

你有一个长度为 $N$ 的数列 $X=(X_1,X_2,\ldots,X_N)$，但你已经忘记了 $X$ 的每个元素的具体值。你还记得以下内容： - （15:18 修正）$X$ 的所有元素都是正整数。 - 对于 $i=1,2,\ldots,P$，有 $X_{A_i}=X_{B_i}$。 - 对于 $i=1,2,\ldots,Q$，有 $X_{C_i}\neq X_{D_i}$。 请在所有满足上述条件的 $X$ 中，输出字典序最小的一个。如果不存在这样的 $X$，请说明。

输入通过标准输入提供，格式如下： > $N$ $P$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_P$ $B_P$ $C_1$ $D_1$ $C_2$ $D_2$ $\vdots$ $C_Q$ $D_Q$

如果存在满足条件的 $X$，请输出其中字典序最小的一个 $Y=(Y_1,Y_2,\ldots,Y_N)$，将 $Y_1,Y_2,\ldots,Y_N$ 用空格分隔输出一行。 如果不存在满足条件的 $X$，请输出 `-1`。

### 样例解释 1 作为 $X$ 可以有 $(2,2,1,2,4)$ 或者 $(100,100,10,100,1)$ 等等，但是 $(1,1,2,1,3)$ 是字典序最小的。 ### 样例解释 2 无法同时满足 $X_1=X_2$ 和 $X_1 \neq X_2$。 ### 数据范围 - $2 \leq N \leq 2\times 10^5$ - $1 \leq P,Q \leq 10^5$ - $1 \leq A_i < B_i \leq N\ (1 \leq i \leq P)$ - $1 \leq C_i < D_i \leq N\ (1 \leq i \leq Q)$ - 输入均为整数。 由 ChatGPT 5 翻译