G - 传递

分值：$600$ 分

问题描述

给定一个简单无向图，有 $N$ 个顶点和 $M$ 条边。$N$ 个顶点依次编号为 Vertex $1$，Vertex $2$，$\ldots$，Vertex $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$ 表示。 此查询涉及以下操作。

1. 令 $X$ 为顶点 $x_i$ 上的整数。
2. 对于与顶点 $x_i$ 相邻的每个顶点，将其上的整数替换为 $X$。

这里，当存在连接它们的边时，称顶点 $u$ 和顶点 $v$ 是相邻的。

按照输入给定的顺序，打印在所有查询处理完成后每个顶点上的整数。

约束

• $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$
• 给定的图是简单的。换言之，它没有自环和重边。
• 输入中的所有数值均为整数。

---

输入

输入从标准输入给出，具体格式如下：

$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

每个查询涉及以下操作。

• 第一个查询 $(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$ 上。）

---

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