RiseOJ – 농장 폐쇄

설명

농부 존과 소들은 긴 휴가를 떠나 마을을 비울 계획이라, 존은 그동안 돈을 아끼기 위해 농장을 임시로 폐쇄하려고 한다.

농장은 $$N$$ 개의 헛간과, 일부 헛간 쌍을 잇는 $$M$$ 개의 양방향 길로 이루어져 있다( $1 \leq N, M \leq 3000$ ). 농장을 폐쇄하기 위해 존은 헛간을 한 번에 하나씩 닫을 계획이다. 헛간이 닫히면 그 헛간에 인접한 모든 길도 함께 닫혀 더 이상 사용할 수 없다.

존은 매 시점(처음, 그리고 헛간을 하나 닫을 때마다)마다 농장이 "완전히 연결"되어 있는지 알고 싶다. 완전히 연결되어 있다는 것은, 열려 있는 임의의 헛간에서 다른 임의의 열려 있는 헛간까지 적절한 길들을 따라 이동할 수 있다는 뜻이다. 존의 농장은 처음부터 다소 낡은 상태라, 시작할 때부터 완전히 연결되어 있지 않을 수도 있다.

문제 출제: 양 리우(Yang Liu)

제약

문제 출제: 양 리우(Yang Liu)

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다. 다음 $$M$$ 개의 줄에는 각 길이 잇는 헛간 쌍이 주어진다(헛간은 $1 \ldots N$ 으로 번호가 매겨져 있다). 마지막 $$N$$ 개의 줄에는 헛간을 닫는 순서를 나타내는 $1 \ldots N$ 의 순열이 주어진다.

출력 형식

출력은 $$N$$ 개의 줄로 이루어지며, 각 줄에는 "YES" 또는 "NO"를 출력한다. 첫째 줄은 처음 상태의 농장이 완전히 연결되어 있는지를 나타내고, $$i+1$$ 번째 줄은 $$i$$ 번째 헛간을 닫은 후 농장이 완전히 연결되어 있는지를 나타낸다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 closing.in · 출력을 쓸 파일 closing.out

예제 1

입력

출력

YES
NO
YES
YES

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > US Open > Silver

올림피아드 > USACO > 2015-2016 > US Open > Silver

태그

JudgeUSACO

농장 폐쇄

평가 및 의견

풀이 제출