시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB132312627.368%

문제

옥토끼나라는 N개의 섬들과 섬들을 연결하는 M개의 다리들로 이루어진, 달에서 이주해 온 토끼들이 사는 자그마한 나라예요! 각각의 다리는 두 개의 섬을 서로 오갈 수 있게 해 주며, 몇 개의 다리들을 건너면 어떠한 두 섬들 간에도 이동이 가능하답니다. 같은 두 섬을 연결하는 다리가 여러 개 있지는 않아요. 평화로운 나날을 보내던 옥토끼나라에 슬프게도 큰 재앙이 닥쳤는데, 바로 전염병이에요. 이 전염병은 무려 라이언을 곰이라 생각하게 되는 끔찍한 질병이에요. (혹시 주변에도 그런 질병이 걸린 사람이 있다면 조심하길 바라요.)

이미 K개나 되는 섬들에 이 전염병이 퍼지고 말았어요. 이 전염병들은 다리를 타고 연결된 다른 섬들의 토끼들까지 전염시키고 말 거예요. 그래서 저희는 섬들을 격리시키는 방안을 생각해냈어요! 하지만 저희는 아직 기술력이 부족해, 단 하나의 섬만을 격리시킬 수 있어요. 섬을 격리시키면 해당되는 섬과 연결된 모든 다리가 사라져요. 다리가 사라진 후, 섬들은 몇 개씩 서로 오갈 수 있는 그룹 여러개로 나타날 거예요. 이때, 그룹에서 T개 이상의 섬들이 감염되어 있으면, 그 그룹 내의 모든 섬은 전염병을 막지 못하고 모두 감염될 거랍니다. 저희를 위해 각 섬을 격리했을때 감염되지 않게 되는 섬의 개수를 구해주세요. 감염된 섬을 격리시켜도 섬 내의 토끼들은 슬프지만 이미 감염되어 있다는 걸 명심해주세요.

입력

첫 줄에 N, M, K, T가 순서대로 주어져요. (2 ≤ N ≤ 3 × 105, 1 ≤ M ≤ 5 × 105, 1 ≤ T ≤ K ≤ N)

다음 M개의 줄은 다리의 정보가 주어진답니다. 두 수가 공백으로 구분되어 주어지는데, 이는 각 수에 해당되는 두 개의 섬을 연결하는 다리가 있다는 뜻이에요. 두 수는 항상 다르고, 1 이상 N 이하에요. 또한, 같은 다리가 여러 번 주어지지 않아요.

마지막에는 이미 감염된 섬들의 번호 K개가 공백으로 구분되어 주어져요. 모든 수는 다 다르고, 모든 수는 1 이상 N 이하에요.

출력

1번 섬부터 순서대로 N번 섬까지 N개의 섬 각각에 대해, 각 섬을 격리했을 때 감염되지 않는 섬의 개수를 공백으로 구분하여 출력해 주세요.

예제 입력 1

4 4 1 1
1 2
1 3
3 4
4 2
1

예제 출력 1

3 1 1 1

출처

Contest > BOJ User Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 D번