G - Propagation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。N 個の頂点はそれぞれ頂点 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 で表されます。 i 番目のクエリでは以下の操作をおこないます。

  1. 頂点 x_i に書かれている整数を X とおく。
  2. 頂点 x_i と隣接するすべての頂点について、それに書かれた整数を X に書き換える。

ただし、頂点 u と頂点 v が隣接するとは、頂点 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

それぞれのクエリでは以下のような操作が行われます。

  • 1 番目のクエリ (x_1 = 1) : 頂点 1 に書かれた整数は 1 であり、頂点 1 に隣接する頂点は頂点 2 と頂点 5 です。 よって、頂点 2 と頂点 5 に書かれた整数がそれぞれ 1 に書き換えられます。
  • 2 番目のクエリ (x_2 = 3) : 頂点 3 に書かれた整数は 3 であり、頂点 3 に隣接する頂点は頂点 2 と頂点 4 です。よって、頂点 2 と頂点 4 に書かれた整数がそれぞれ 3 に書き換えられます。
  • 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

Score : 600 points

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