AT_pakencamp_2024_day2_h Hold a Contest

パ研王国には $ N $ 人の住人がいて、 $ 1 $ から $ N $ までの番号がつけられています。パ研王国の住人には競技プログラミングの強さを表すレーティングという値が定められていて、住人 $ i $ $ (1 \leq i \leq N) $ のレーティングは $ R_i $ です。 また、この $ N $ 人の間には $ M $ 個の友達関係があり、住人 $ A_j $ と住人 $ B_j $ $ (1 \leq j \leq M) $ は友達です。この $ M $ 個の友達関係以外に友達である住人の組は存在しません。 パ太郎はパ研王国の住人を対象に競技プログラミングのコンテストを開くことにしました。パ太郎はまずレーティング制限 $ X $ ( $ X $ は整数) を定め、その後 $ N $ 人の住人のうち $ K $ 人を任意に選び、招待状を送ることにしました。 パ太郎または他の住人から招待状を受け取った住人 $ x $ $ (1 \leq x \leq N) $ は次のように行動します。 - 既に $ 1 $ 枚以上の招待状を受け取っていた場合、何もしない。 - それまでに招待状を受け取っておらず、自身のレーティングがレーティング制限以上である場合、すなわち $ X \leq R_x $ の場合、コンテストに参加し、さらに自分の友達であるような住人全員に新たに招待状を送る。 - それ以外の場合、何もしない。 パ太郎はコンテストのレベルを高めるためできるだけレーティング制限を大きくしたいですが、参加者が少なすぎると困ってしまいます。 そこでパ太郎は $ N $ 個の質問を考えました。 $ k $ $ (1 \leq k \leq N) $ 番目の質問は、次のようなものです。 - $ k $ 人以上の住人がコンテストに参加するためにはレーティング制限を最大でいくつにできるだろうか？ただし、招待状を送る $ K $ 人の住人は自由に選べるものとする。 パ太郎のために、この $ N $ 個の質問に答えるプログラムを作成してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ R_1 $ $ R_2 $ $ \ldots $ $ R_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

標準出力に $ N $ 行で出力せよ。 $ k $ 行目には、 $ k $ 番目の質問に対する答えを整数で出力せよ。ただし、レーティング制限をどのように設定しても $ k $ 人以上の住人がコンテストに参加することができない場合、 $ -1 $ を出力せよ。

### 小課題 1. ( $ 1 $ 点) $ N \leq 2 $ 2. ( $ 2 $ 点) $ M = 0 $ 3. ( $ 2 $ 点) $ N \leq 10 $ 4. ( $ 10 $ 点) $ R_i = 1 $ $ (1 \leq i \leq N) $ 5. ( $ 10 $ 点) $ R_i \leq 5 $ $ (1 \leq i \leq N) $ 6. ( $ 20 $ 点) $ K = 1 $ 7. ( $ 30 $ 点) $ K \leq 5 $ 8. ( $ 25 $ 点) 追加の制約はない ### Sample Explanation 1 例えば、 $ k=3 $ のとき、 $ X=2 $ とすれば条件を満たすことができます。具体的には、住人 $ 2 $ に招待状を送ると、住人 $ 2 $ が住人 $ 3 $ に、住人 $ 3 $ が住人 $ 4 $ に招待状を送るため、最終的には住人 $ 2,3,4 $ の $ 3 $ 人が参加することで条件を満たします。なお、住人 $ 2 $ は住人 $ 1 $ にも招待状を送りますが、住人 $ 1 $ のレーティングは $ X $ 未満であるため、住人 $ 1 $ はコンテストには参加しません。 このサンプルは小課題 $ 3, 5, 6, 7, 8 $ の制約を満たします。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 0 \leq M \leq 2 \times 10^5 $ - $ 1 \leq K \leq N $ - $ 1 \leq R_i \leq 10^{18} $ $ (1 \leq i \leq N) $ - $ 1 \leq A_i