← 返回题目列表

AtCoder · abc219_g

G. 传播

中文机器翻译题面 查看原题

分数: 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。 该查询涉及以下操作。

  1. 让 X 是写在 Vertex 上的整数 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 表示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