102196: [AtCoder]ABC219 G - Propagation

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The $N$ vertices are called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$.
For each $i = 1, 2, \ldots, M$, the $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.
Additionally, for each $i = 1, 2, \ldots, N$, Vertex $i$ has an integer $i$ written on it.

You are also given $Q$ queries.
For each $i = 1, 2, \ldots, Q$, the $i$-th query is represented as an integer $x_i$. This query involves the following operation.

1. Let $X$ be the integer written on Vertex $x_i$.
2. For every vertex adjacent to Vertex $x_i$, replace the integer written on it with $X$.

Here, Vertex $u$ and Vertex $v$ are said to be adjacent when there is an edge connecting them.

Print the integer written on each vertex after all queries are processed in the order they are given from input.

Constraints

• $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$
• The given graph is simple. In other words, it has no self-loops and no multi-edges.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $Q$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$x_1$ $x_2$ $\ldots$ $x_Q$

Output

Print the integers written on the vertices after all queries are processed, in the format below, with spaces in between.
Here, for each $i = 1, 2, \ldots, N$, $A_i$ denotes the integer written on Vertex $i$.

$A_1$ $A_2$ $\ldots$ $A_N$

Sample Input 1

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

Sample Output 1

1 3 3 3 3

Each query involves the following operation.

• The first query $(x_1 = 1)$: Vertex $1$ has the integer $1$ written on it, and the vertices adjacent to Vertex $1$ are Vertices $2$ and $5$. Thus, the integers on Vertices $2$ and $5$ get replaced with $1$.
• The second query $(x_2 = 3)$: Vertex $3$ has the integer $3$ written on it, and the vertices adjacent to Vertex $3$ are Vertices $2$ and $4$. Thus, the integers on Vertices $2$ and $4$ get replaced with $3$.
• The third query $(x_3 = 4)$: Vertex $4$ has the integer $3$ written on it, and the vertices adjacent to Vertex $4$ are Vertices $2$, $3$, and $5$. Thus, the integers on Vertices $2$, $3$, and $5$ get replaced with $3$. (Vertices $2$ and $3$ already have $3$ written on them, so the actual change takes place only on Vertex $5$.)

Sample Input 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

Sample Output 2

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

问题描述

给你一个有N个顶点和M条边的简单无向图。这N个顶点分别被称为顶点1、顶点2、...、顶点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_i$上的整数设为X。
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