传播

题目描述

给你一个具有 $N$ 个顶点和 $M$ 条边的简单无向图。这些顶点称为顶点 $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$ 表示。 该查询涉及以下操作：

设 $X$ 为顶点 $x_i$ 上写的整数。

对于与顶点 $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$

样例

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

1 3 3 3 3

每个查询进行如下操作。

第 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$。）

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 \le N \le 2 \times 10^5$
• $0 \le M \le \min(2 \times 10^5, N(N-1)/2)$
• $1 \le Q \le 2 \times 10^5$
• $1 \le u_i, v_i \le N$
• $1 \le x_i \le N$
• 给定的图是简单图。也就是说，没有自环，也没有重边。
• 输入中的所有值均为整数