Tuyến đường gần nhất

Đất nước Ukraine có $n$ thành phố, đánh số từ $1$ đến $n$. Các thành phố được nối với nhau bởi hệ thống giao thông gồm $m$ tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng $b$ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng Ukraine Denys Shmyhal đã chọn ra $r$ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì. Một thành phố có thể vừa có kho lương thực vừa có trại quân sự, khi đó kết quả của nó bằng $0$.

Dữ liệu vào

• Dòng thứ nhất gồm bốn số nguyên $n,m,b,r$.
• Dòng thứ hai gồm $b$ số nguyên đôi một khác nhau là chỉ số của các thành phố được đặt kho lương thực.
• Dòng thứ ba gồm $r$ số nguyên đôi một khác nhau là chỉ số của các thành phố được đặt trại quân sự.
• $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u$ và $v$ ($1\le u,v\le n$, $u\ne v$) thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố $u$ và $v$.

Dữ liệu ra

In ra $r$ số nguyên trên cùng một dòng, cách nhau bởi dấu cách, là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu vào.

Ràng buộc

• $2\le n\le 5·{10}^5$; $1\le m\le 5·{10}^5$.
• $1\le b,r\le n$.
• Đồ thị liên thông, không có hai tuyến đường nối cùng một cặp thành phố.

Subtasks

• Subtask 1 ($40\%$ số test): $2\le n\le 2000$; $1\le m\le 2000$.
• Subtask 2 ($60\%$ số test): không có ràng buộc gì thêm.

Bài được chấm theo từng test, mỗi test có cùng số điểm.

Ví dụ