← 返回题目列表

AtCoder · pakencamp_2022_day1_i

I. 被遗忘的序列

中文机器翻译题面 查看原题

配点 : 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 不能同时满足。