{"code":"hsgtrkholuong","name":"Kho lương (HSG10v2-2022)","description":"Sau khi chiến thắng quân xâm lược, nhà vua của đất nước Islanders muốn xây dựng hệ thống doanh trại quân sự tại các ngôi làng để củng cố vững chắc nền độc lập của mình. Đất\r\nnước có $n$ ngôi làng được đánh số từ $1$ đến $n$ và các ngôi làng này được nối với nhau bởi hệ\r\nthố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 ngôi\r\nlàng, đảm bảo luôn có đường đi lại giữa hai ngôi làng bất kì trong nước (trực tiếp hoặc đi\r\nqua một số ngôi làng khác). Giữa hai ngôi làng bất kì không có quá một tuyến đường nối\r\ntrực tiếp. Nhà vua 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\r\nở một ngôi làng khác nhau. Sau khi họp với các tướng lĩnh, nhà vua đã chọn ra $r$ ngôi làng\r\nkhác nhau để đặt doanh trại quân sự.\r\nYêu cầu với mỗi ngôi làng được đặt doanh trại quân sự, nhiệm vụ của bạn là tính toán số\r\ntuyến đường ít nhất cần đi nếu xuất phát từ ngôi làng đó đến một kho lương thực bất kì.\r\n\r\n

Input

\r\n\r\nVào từ file văn bản KHOLUONG.INP:\r\n- Dòng thứ nhất gồm bốn số nguyên: $n, m, b, r(2 \\le n \\le 5.10^5;1 \\le m \\le 5.10^5;1 \\le b, r \\le n)$.\r\n- Dòng thứ hai gồm $b$ số nguyên là chỉ số của các ngôi làng được đặt kho lương.\r\n- Dòng thứ ba gồm $r$ số nguyên là chỉ số của các ngôi làng được đặt doanh trại.\r\n- $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u$ và $v$ thể hiện có một tuyến đường\r\nhai chiều nối trực tiếp hai ngôi làng $u$ và $v$.\r\n\r\n

Output

\r\n\r\nGhi ra file văn bản KHOLUONG.OUT:\r\n- 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 ngôi làng được đặt\r\ndoanh trại quân sự theo thứ tự của dữ liệu vào.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($40\\%$ số điểm): $2 \\le n \\le 2000, 1 \\le m \\le 2000$\r\n- Subtask $2$ ($60\\%$ số điểm): Không có ràng buộc gì thêm\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6 6 2 3\r\n 3 2\r\n 1 5 4\r\n 1 2\r\n 1 6\r\n 3 6\r\n 2 3\r\n 4 5\r\n 3 4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1 2 1\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n - Ngôi làng 1: 1 → 2\r\n - Ngôi làng 4: 4 → 3\r\n - Ngôi làng 5: 5 → 4 → 3","points":300.0,"partial":true,"time_limit":3.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}