配点 : 400 点
問題文
你是长度 我有 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 不存在,请报告。 如果存在可能的
制約
- 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)
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
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
5 2 3 1 2 2 4 1 3 4 5 3 5
出力例 1
1 1 2 1 3
X 还有 (2,2,1,2,4) 呀 (100,100,10,100,1) 等。(1,1,2,1,3) 按字典顺序是最小的。
入力例 2
5 1 1 1 2 1 2
出力例 2
-1
X_1=X_2 和 在 X_1\neq X_2 不能同时满足。