Problem
우리가 이름을 밝힐 수 없는 극비 조직 중 하나는
N개의 지하 벙커 네트워크로 동일한 길이의 터널로 연결되어 있으며 이 터널을 통해 모든 벙커에서 다른 벙커로 이동할 수 있습니다( 반드시 직접적으로는 아님). 외부 세계와의 통신은 일부 벙커에 위치한 특수 비밀 출구를 통해 이루어집니다.
조직은 비상 시 직원 대피 계획을 작성해야 했습니다. 이렇게 하려면 각 벙커에 대해 가장 가까운 출구까지 걸리는 시간을 알아야 합니다. 이러한 작업의 전문가인 귀하는 극비 조직 구내에 대한 주어진 설명에 따라 각 벙커에 필요한 시간을 계산하도록 지시받습니다. 편의를 위해 벙커는
1에서
N까지 번호가 매겨져 있습니다.
입력:
- 처음 두 줄은 두 개의 자연수
N,
K를 포함합니다(
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — 벙커의 수와 출구의 수;
- 세 번째 줄에는
1에서
N 사이의 공백으로 구분된
K 숫자로 출구가 위치한 벙커의 번호를 나타냅니다.
- 네 번째 줄에는 숫자
M(
\(1 <= M <= 100000\)) — 터널 수;
- 다음
M에서 행은 숫자 쌍을 입력합니다 – 터널로 연결된 벙커의 수.
각 터널은 양방향으로 이동할 수 있습니다. 조직에는 벙커에서 자체로 이어지는 터널이 없지만 한 쌍의 벙커 사이에는 터널이 두 개 이상 있을 수 있습니다.
출력: 공백으로 구분된 숫자
N개 인쇄 — 각 벙커에 대해 출구에 도달하는 데 필요한 최소 시간입니다. 하나의 터널을 통과하는 시간이
1이라고 가정합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
3
1
2
3
1 2
3 1
2 3
| 101 |
| 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 |