题目描述

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。$N$ 個の頂点はそれぞれ頂点 $1$ 、頂点 $2$ 、$\ldots$ 、頂点 $N$ と呼ばれます。
$i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。
また、$i\ =\ 1,\ 2,\ \ldots,\ N$ について、頂点 $i$ には整数 $i$ が書かれています。

$Q$ 個のクエリが与えられます。
$i\ =\ 1,\ 2,\ \ldots,\ Q$ について、$i$ 番目のクエリは整数 $x_i$ で表されます。 $i$ 番目のクエリでは以下の操作をおこないます。

1. 頂点 $x_i$ に書かれている整数を $X$ とおく。
2. 頂点 $x_i$ と隣接するすべての頂点について、それに書かれた整数を $X$ に書き換える。

ただし、頂点 $u$ と頂点 $v$ が隣接するとは、頂点 $u$ と頂点 $v$ を結ぶ辺が存在することを言います。

入力で与えられる順にすべてのクエリを処理した後の時点における、各頂点に書かれた整数をそれぞれ出力して下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

すべてのクエリを処理した後の時点における、各頂点に書かれた整数を以下の形式で空白区切りで出力せよ。
ただし、$i\ =\ 1,\ 2,\ \ldots,\ N$ について $A_i$ は頂点 $i$ に書かれた整数を表す。

$A_1$ $A_2$ $\ldots$ $A_N$

题目大意

给你一个 $n$ 个点 $m$ 条边的无向图, 每个点上有数 $a_i$. 初始情况下, $a_i=i$.

现在进行 $q$ 次操作, 每次给定一个数 $u$. 对于所有与 $u$ 直接相连的点 $v$, 把 $a_v$ 改为 $a_u$.

所有操作后, 求 $a$ 序列.

$n,m,q \le 2\times 10^5$.

5 6 3
4 2
4 3
1 2
2 3
4 5
1 5
1 3 4

1 3 3 3 3

14 14 8
7 4
13 9
9 8
4 3
7 2
13 8
12 8
11 3
6 3
7 14
6 5
1 4
10 13
5 2
2 6 12 9 1 10 5 4

1 6 1 1 6 6 1 9 9 10 11 12 10 14

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $ 0\ \leq\ M\ \leq\ \min(2\ \times\ 10^5,\ N(N-1)/2) $
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ u_i,\ v_i\ \leq\ N$
• $1\ \leq\ x_i\ \leq\ N$
• 与えられるグラフは単純である。すなわち、自己ループや多重辺は存在しない。
• 入力はすべて整数

Sample Explanation 1

それぞれのクエリでは以下のような操作が行われます。 - $1$ 番目のクエリ $(x_1\ =\ 1)$ : 頂点 $1$ に書かれた整数は $1$ であり、頂点 $1$ に隣接する頂点は頂点 $2$ と頂点 $5$ です。 よって、頂点 $2$ と頂点 $5$ に書かれた整数がそれぞれ $1$ に書き換えられます。 - $2$ 番目のクエリ $(x_2\ =\ 3)$ : 頂点 $3$ に書かれた整数は $3$ であり、頂点 $3$ に隣接する頂点は頂点 $2$ と頂点 $4$ です。よって、頂点 $2$ と頂点 $4$ に書かれた整数がそれぞれ $3$ に書き換えられます。 - $3$ 番目のクエリ $(x_3\ =\ 4)$ : 頂点 $4$ に書かれた整数は $3$ であり、頂点 $4$ に隣接する頂点は頂点 $2$ 、頂点 $3$ 、頂点 $5$ です。よって、頂点 $2$ 、頂点 $3$ 、頂点 $5$ に書かれた整数がそれぞれ $3$ に書き換えられます。 （頂点 $2$ と頂点 $3$ にはすでに $3$ が書かれているので、書かれた整数が実際に変更されるのは頂点 $5$ のみです。）