Có một trò chơi trên bàn dành cho \(K\) người chơi. Bàn chơi gồm \(N\) ô được đánh số từ \(1\) đến \(N\) và \(M\) đường đi được đánh số từ \(1\) đến \(M\). Đường đi \(j\) \((1 \le j \le M)\) nối hai ô \(U_j\) và \(V_j\) theo cả hai chiều.

Mỗi ô thuộc một trong hai loại: ô đi tiếp hoặc ô dừng. Thông tin này được mô tả bởi xâu \(S\) có độ dài \(N\), chỉ gồm các ký tự 0 và 1: ký tự thứ \(i\) là 0 nếu ô \(i\) là ô đi tiếp, và là 1 nếu ô \(i\) là ô dừng.

\(K\) người chơi được đánh số từ \(1\) đến \(K\). Mỗi người có một quân cờ của riêng mình. Ban đầu, người chơi \(p\) đặt quân cờ ở ô \(X_p\) \((1 \le p \le K)\). Nhiều quân cờ có thể cùng nằm trên một ô.

Các người chơi lần lượt thực hiện lượt của mình, bắt đầu từ người chơi \(1\) và theo thứ tự tăng dần. Sau lượt của người chơi \(p\) là lượt của người chơi \(p+1\); sau người chơi \(K\) lại đến người chơi \(1\). Trong lượt của mình, một người chơi thực hiện các thao tác sau:

1. Chọn một ô được nối trực tiếp bằng một đường đi với ô đang chứa quân cờ của mình, rồi di chuyển quân cờ đến ô đã chọn.
2. Nếu ô vừa đến là ô đi tiếp, quay lại bước \(1\) và tiếp tục lượt của mình. Nếu đó là ô dừng, kết thúc lượt.

Đội tuyển Nhật Bản gồm \(K\) thành viên, trong đó có JOI-kun, đang nghiên cứu cách phối hợp để hoàn thành trò chơi thật nhanh. Họ quan tâm đến câu hỏi: tổng số lần di chuyển ít nhất của cả \(K\) người chơi để đưa quân cờ của người chơi \(1\) đến ô \(T\) là bao nhiêu? Điều kiện được coi là thỏa mãn ngay khi quân cờ của người chơi \(1\) đến ô \(T\), kể cả khi lượt hiện tại chưa kết thúc.

Cho thông tin về bàn chơi và vị trí ban đầu của các quân cờ, hãy tính câu trả lời cho từng \(T=1,2,\ldots,N\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M K
U_1 V_1
U_2 V_2
...
U_M V_M
S
X_1 X_2 ... X_K

Dữ liệu ra

In \(N\) dòng ra đầu ra chuẩn. Dòng thứ \(T\) \((1 \le T \le N)\) chứa tổng số lần di chuyển ít nhất của cả \(K\) người chơi để đưa quân cờ của người chơi \(1\) đến ô \(T\).

Ràng buộc

• \(2 \le N \le 50\,000\).
• \(1 \le M \le 50\,000\).
• \(2 \le K \le 50\,000\).
• \(1 \le U_j < V_j \le N\) \((1 \le j \le M)\).
• \((U_j,V_j) \ne (U_k,V_k)\) với mọi \(1 \le j < k \le M\).
• Từ một ô bất kỳ có thể đi đến mọi ô khác bằng cách đi qua một số đường đi.
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự 0, 1.
• \(1 \le X_p \le N\) \((1 \le p \le K)\).
• \(N,M,K,U_j,V_j,X_p\) đều là số nguyên.

Phân nhóm

• Nhóm 1 (3 điểm): Không có ô dừng.
• Nhóm 2 (7 điểm): Có đúng một ô dừng.
• Nhóm 3 (7 điểm): Có đúng hai ô dừng.
• Nhóm 4 (19 điểm): \(N \le 3\,000\), \(M \le 3\,000\), \(K \le 3\,000\).
• Nhóm 5 (23 điểm): \(K=2\).
• Nhóm 6 (9 điểm): \(K \le 100\).
• Nhóm 7 (23 điểm): \(N \le 30\,000\), \(M \le 30\,000\), \(K \le 30\,000\).
• Nhóm 8 (9 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5 2
1 2
2 3
2 4
3 5
4 5
00000
1 5

0
1
2
2
3

5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

0
1
4
4
5

5 5 2
1 2
2 3
2 4
3 5
4 5
01100
1 5

0
1
3
3
4

8 7 5
1 3
5 7
4 6
2 6
2 3
7 8
1 5
10011010
4 6 4 7 1

4
2
3
0
10
1
17
24

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

0
1
4
5
6
7
8
8
4
1
13
9

Nguồn

Nguồn: JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ hai (22/03/2024). Đề bài của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.