AT_abc219_g [ABC219G] Propagation

给定一个有 $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$

### 约束条件 - $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$ - 给定的图是简单图，即不存在自环或重边。 - 输入均为整数。 ### 样例说明 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 的整数发生了变化。） 由 ChatGPT 4.1 翻译