Propagation

题目描述

你被给定了一个含有 $N$ 个顶点和 $M$ 条边的简单无向图。$N$ 个顶点被称为 Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$.
对于每个 $i = 1, 2, \ldots, M$，第 $i$ 条边连接 Vertex $u_i$ 和 Vertex $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

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$ 给定的图是简单的。换句话说，它没有自环也没有多重边。 输入中的所有数值均为整数。每个查询涉及以下操作。

第一个查询 $(x_1 = 1)$: 顶点 $1$ 写着整数 $1$，与顶点 $1$ 相邻的顶点是顶点 $2$ 和顶点 $5$。 因此，顶点 $2$ 和顶点 $5$ 上的整数被替换为 $1$。 第二个查询 $(x_2 = 3)$: 顶点 $3$ 写着整数 $3$，与顶点 $3$ 相邻的顶点是顶点 $2$ 和顶点 $4$。 因此，顶点 $2$ 和顶点 $4$ 上的整数被替换为 $3$。 第三个查询 $(x_3 = 4)$: 顶点 $4$ 写着整数 $3$，与顶点 $4$ 相邻的顶点是顶点 $2$、3 和 5。 因此，顶点 $2$、3 和 5 上的整数被替换为 $3$。 （顶点 $2$ 和 $3$ 已经写着 $3$，所以实际变化只发生在顶点 $5$。）

标签: AtCoder|abc219G

来源

AtCoder|abc219G