파일 업로드

공원 폐쇄

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

도시의 시장인 이성민은시의 예산을 아끼기 위해 도시 안의 몇 개의 공원을 잠시 폐쇄하기로 결정했습니다.

도시에는 NN개의 공원이 있으며, 몇몇 공원 사이에는 연결된 MM개의 양방향 길들이 있습니다 (1N,M30001 \leq N, M \leq 3000). 도시를 잠시 닫기 위해, 이성민은 한 번에 하나씩 공원을 폐쇄할 계획입니다. 공원이 폐쇄되면, 해당 공원에 인접한 모든 길들도 폐쇄되며, 더 이상 사용할 수 없게 됩니다.

이성민은 각 시점마다 (최초 및 각 폐쇄 후) 그의 도시가 "완전히 연결되어 있는지" (즉, 오픈된 모든 공원에서 다른 모든 오픈된 공원으로 적절한 길들을 따라 이동할 수 있는지) 알고 싶습니다. 처음에 이성민의 도시는 어느 정도 황폐한 상태이므로, 완전히 연결되어 있지 않을 수도 있습니다.

💻 입력

입력의 첫 번째 줄에는 NNMM이 포함됩니다. 다음 MM개의 줄 각각은 연결된 공원의 쌍을 설명하는 길을 나타냅니다 (공원은 편리하게 1N1 \ldots N으로 번호가 매겨져 있습니다). 마지막 NN줄은 공원이 폐쇄될 순서를 나타내는 1N1 \ldots N의 순열을 제공합니다.

🖨️ 출력

출력은 NN개의 줄로 구성되며, 각 줄은 "YES" 또는 "NO"를 포함합니다. 첫 번째 줄은 초기 도시가 완전히 연결되어 있는지를 나타내고, i+1i+1번째 줄은 ii번째 폐쇄 후 도시가 완전히 연결되어 있는지를 나타냅니다.


💻 예제 입력 1
4 3
1 2
2 3
3 4
3
4
1
2
🖨️ 예제 출력 1
YES
NO
YES
YES

출처: USACO 2016 US Open Contest, Silver Problem 3. Closing the Farm