I - Forgotten Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 を同時に満たすことはできません。