Problem
極秘組織の 1 つ (その名前を明らかにすることは許可されていません) は、同じ長さのトンネルで接続された
N 個の地下壕のネットワークであり、どの地下壕から他の壕にも移動できます (必ずしも直接的ではありません）。外部との通信はバンカーの一部にある特別な秘密の出口を通して行われ
ます。
この組織は、緊急事態に備えてスタッフの避難計画を作成する必要がありました。これを行うには、各バンカーについて、最寄りの出口までにかかる時間を調べる必要があります。このような任務の専門家であるあなたは、極秘組織の敷地に関する所定の説明に従って、各バンカーに必要な時間を計算するよう指示されます。便宜上、バンカーには
1 から
N までの番号が付けられています。
入力:
- 最初の 2 行には 2 つの自然数
N、
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) —それぞれバンカーの数と出口の数;
- 3 行目では、スペースで区切られた
1 から
N までの
K 個の異なる数字で、出口があるバンカーの番号を示します。
- 4 行目には数値
M (
\(1 <= M <= 100000\)) が含まれています。トンネルの数;
- 次の
M 内 行には数字のペアを入力します。トンネルで結ばれたバンカーの数
各トンネルは両方向に移動できます。組織にはバンカーから組織自体につながるトンネルはありませんが、2 つのバンカー間に複数のトンネルが存在する可能性があります。
出力: N 個のスペース区切りの数字を出力します。各バンカーについて、出口に到達するまでに必要な最小時間。 1 つのトンネルを通過するのにかかる時間が
1 であると仮定します。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |