问题描述

给定一个简单无向图，有 $N$ 个顶点和 $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$

示例输入 1

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

示例输出 1

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

示例输入 2

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

示例输出 2

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