COCI 2019/2020 - Contest 6 - Birmingham

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ở thành phố Birmingham, mọi người rất quan tâm đến các cuộc đua ngựa. Tuy nhiên ít ai biết rằng người chiến thắng các cuộc đua được quyết định trong những cuộc họp kín trước cả khi cuộc đua thực sự diễn ra. Những người dự họp sau khi tan họp về nhà sẽ bắt đầu truyền thông tin ra khắp thành phố.

Ngày đầu tiên sau cuộc họp, những người sống cách không quá ~K~ (~K~ là hệ số cho trước) bước từ nhà của một người đã biết tin sẽ biết được người chiến thắng đã được quyết định. Ngày thứ hai sau cuộc họp, những người sống cách nhà của một người đã biết tin không quá ~2 \cdot K~ bước sẽ biết được người chiến thắng. Tổng quát hơn, ~X~ ngày sau cuộc họp thì những người sống cách không quá ~X \cdot K~ bước từ một người đã biết tin sẽ biết được người chiến thắng.

Thành phố Birmingham được biểu diễn dưới dạng đồ thị vô hướng. Mỗi nhà được đánh số từ ~1~ đến ~N~ và hai nhà liền kề được nối bởi một con đường. Có thể qua lại những nhà không kề nhau thông qua một hay nhiều con đường.

Với mỗi nhà, xác định chủ nhà sẽ biết được người chiến thắng sớm nhất khi nào.

Input

  • Dòng đầu tiên chứa 4 số nguyên dương ~N~, ~M~, ~Q~, ~K~ (~N, Q, K \leq 10^5~, ~M \leq 2 \cdot 10^5~) là số căn nhà trong thành phố, số con đường, số người đã dự họp và hệ số ~K~ trong đề bài.
  • Dòng tiếp theo chứa ~Q~ số nguyên dương cho biết những căn nhà có người dự họp.
  • Mỗi dòng trong ~M~ dòng tiếp theo chứa 2 số nguyên dương ~A~, ~B~ cho biết có đường nối trực tiếp giữa 2 căn nhà ~A~ và ~B~.

Output

Với mỗi căn nhà ở Birmingham, cho biết ngày sớm nhất mà chủ nhà biết tin. Quy ước rằng nếu chủ nhà dự họp thì ngày biết tin là ngày ~0~.

Ví dụ

Sample input 1
6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
Sample output 1
1 1 2 2 1 0
Sample input 2
6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
Sample output 2
1 1 1 0 1 0
Sample input 3
6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
Sample output 3
1 1 1 2 1 0

Ghi chú

Giải thích cho ví dụ 3: Vì nhà ~1~, ~2~, ~3~ và ~5~ đều cách nhà ~6~ không quá ~2~ bước nên chủ những nhà ấy sẽ biết tin ~1~ ngày sau ngày họp. Chủ nhà ~4~ sẽ biết tin sau ~2~ ngày.


Comments

Please read the guidelines before commenting.



  • 2
    manager   commented on Sept. 5, 2021, 8:24 p.m.

    à hóa ra là cách X.K bước từ nhà của người đã biết tin chứ để người dự họp lại nhầm với Q :))


  • -1
    manager   commented on Sept. 5, 2021, 6:29 p.m.

    test 1 là ntn nhở