Nguồn đề: Beginner Free Contest 28

Đề bài: https://drive.google.com/file/d/1ZqYBoUEHEFYfkRQBgMNRVJbAzo91utlK/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1Oc4FkVQeGOctovtnjWJ2aB9eO18meGGO/view?usp=sharing

Đất nước X xinh đẹp 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 đặ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 đã chọn ra r thành phố khác nhau để đặt trại quân sự.

Để 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ì.

Input

Dòng 1: Gồm 4 số nguyên n, m, b, r ~(2 ≤ n ≤ 5.10^5, 1 ≤ m ≤ 5.10^5, 1 ≤ b, r ≤ n).~

Dòng 2: Gồm b số nguyên ~b_i~ là chỉ số của các thành phố đặt kho lương thực ~(1 \leq b_i \leq n)~

Dòng 3: Gồm r số nguyên ~r_i~ là chỉ số của các thành phố đặt trại quân sự ~(1 \leq r_i \leq n)~

m dòng tiếp theo, mỗi dòng gồm 2 số nguyên u và v thể hiện có một tuyến đường 2 chiều nối trực tiếp hai thành phố u và v

Kết quả

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

Sample Input

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

Sample Output

1 2 1

Giải thích

• Thành phố 1: 1->2
• Thành phố 4: 4->3
• Thành phố 5: 5->4->3