Problem
Một trong những Tổ chức Tối mật mà chúng tôi không được phép tiết lộ tên, là một mạng lưới
N boong-ke ngầm được nối với nhau bằng các đường hầm có chiều dài bằng nhau, qua đó người ta có thể đi từ bất kỳ boong-ke nào đến bất kỳ hầm nào khác ( không nhất thiết phải trực tiếp). Việc liên lạc với thế giới bên ngoài được thực hiện thông qua các lối thoát hiểm bí mật đặc biệt nằm ở một số boong-ke.
Tổ chức cần lập một kế hoạch sơ tán nhân viên trong trường hợp khẩn cấp. Để làm điều này, đối với mỗi boongke, bạn cần tìm hiểu xem sẽ mất bao lâu để đến lối ra gần nhất. Bạn, với tư cách là một chuyên gia trong các nhiệm vụ như vậy, được hướng dẫn tính toán thời gian cần thiết cho từng boong-ke theo mô tả nhất định về cơ sở của Tổ chức Tối mật. Để thuận tiện cho bạn, các boong-ke được đánh số từ
1 đến
N.
Đầu vào:
- 2 dòng đầu ghi 2 số tự nhiên
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — số lượng boong-ke và số lượng lối ra tương ứng;
- ở dòng thứ ba, các số khác nhau
K được phân tách bằng dấu cách từ
1 đến
N, cho biết số lượng boong-ke nơi có lối ra;
- dòng thứ tư chứa số
M (
\(1 <= M <= 100000\)) — số lượng đường hầm;
- trong
M dòng nhập các cặp số – số lượng boongke được nối với nhau bằng một đường hầm.
Mỗi đường hầm có thể di chuyển theo cả hai hướng. Một tổ chức không có đường hầm dẫn từ boong-ke đến tổ chức, nhưng có thể có nhiều đường hầm giữa một cặp boong-ke.
Đầu ra: in
N các số được phân tách bằng dấu cách — đối với mỗi boongke, thời gian tối thiểu cần thiết để đến lối ra. Giả sử rằng thời gian để đi qua một đường hầm là
1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 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 |