分数: 600 点
问题陈述
给你一个简单的无向图 N 顶点和 M 边缘。的 N 顶点称为 Vertex 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 是写在 Vertex 上的整数 x_i.
- 对于与顶点相邻的每个顶点 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 表示Vertex上写入的整数 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 ,和Vertex相邻的顶点 1 是顶点 2 和 5。 因此,顶点上的整数 2 和 5 被替换为 1.
- 第二次查询 (x_2 = 3):顶点 3 具有整数 上面写着 3 ,和Vertex相邻的顶点 3 是顶点 2 和 4。 因此,顶点上的整数 2 和 4 被替换为 3.
- 第三次查询 (x_3 = 4):顶点 4 具有整数 上面写着 3 ,和Vertex相邻的顶点 4 是顶点 2, 3,和 5。 因此,顶点上的整数 2, 3,和 5 被替换为 3。 (顶点 2 和 3 已经有 3 写在它们上面,所以实际的改变只发生在 Vertex 上 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