JOI có \(N\) thành phố, đánh số từ 1 đến \(N\); thành phố 1 là thủ đô. Có \(M\) tuyến đường sắt hai chiều, tuyến \(i\) nối \(U_i\) và \(V_i\). Có thể đi giữa mọi cặp thành phố bằng đường sắt.

Ban đầu mọi tuyến có giá 1 yên. Trong \(Q\) năm tới, vào đầu năm \(j\), giá tuyến \(R_j\) tăng từ 1 lên 2 yên và giữ nguyên sau đó; không tuyến nào tăng giá hai lần.

Sau lần tăng giá mỗi năm, một thành phố \(k\) (\(2\le k\le N\)) bất mãn khi và chỉ khi chi phí nhỏ nhất từ \(k\) tới thủ đô theo giá hiện tại lớn hơn chi phí nhỏ nhất ban đầu. Chi phí một hành trình là tổng giá các tuyến đã đi. Thành phố 1 không bao giờ bất mãn.

Hãy tính số thành phố bất mãn trong từng năm.

Dữ liệu vào

• Dòng đầu chứa \(N,M,Q\).
• \(M\) dòng tiếp theo: dòng \(i\) chứa \(U_i,V_i\).
• \(Q\) dòng tiếp theo: dòng \(j\) chứa \(R_j\).

Dữ liệu ra

In ra \(Q\) dòng; dòng \(j\) là số thành phố bất mãn trong năm \(j\).

Ràng buộc

• \(2\le N\le100000\).
• \(1\le Q\le M\le200000\).
• \(1\le U_i,V_i\le N\) và \(U_i\ne V_i\).
• \(1\le R_j\le M\); các \(R_j\) đôi một khác nhau.
• Giữa hai thành phố có nhiều nhất một tuyến trực tiếp.
• Mọi thành phố đều có đường tới thành phố 1.

Phân nhóm

• Nhóm 1 (12 điểm): \(N\le100\), \(M\le4950\), \(Q\le30\).
• Nhóm 2 (14 điểm): \(Q\le30\).
• Nhóm 3 (35 điểm): các số nguyên xuất hiện trong đáp án đúng có không quá 50 giá trị khác nhau.
• Nhóm 4 (39 điểm): không có ràng buộc bổ sung.

Ví dụ

5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3

0
2
2
4
4

4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6

1
1
2
2
3
3

2 1 1
1 2
1

1

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 3.