問題
대한민국은 N개의 도시와 M개의 양방향 도로로 나타낼 수 있다.
안타깝게도, 대한민국은 적국으로부터 폭격을 받고 있다. 적군은 모든 도시를 정확히 한 번씩 폭격한다.
도시가 폭격을 받으면, 그 도시와 인접한 도로들도 모두 사라진다.
장태환은 적국의 폭격 순서를 입수했다. 이제 적군이 순서대로 i개 도시를 폭격했을 때, 폭격받지 않은 도시들이 모두 연결되었는지 여부를 구해보자.
(단, 대한민국이 모두 연결되지 않은 상태로 폭격이 시작될 수도 있다.)
入力
첫째 줄에 N,M이 주어진다. (1≤N,M≤200,000)
두 번째 줄부터 M줄 동안 대한민국의 도로들이 잇는 도시의 번호들이 주어진다.
그 뒤로 N줄 동안 적국이 도시를 폭격하는 순서가 주어진다.
出力
i번째 줄에 적군이 i-1개의 도시를 폭격했을 때의 연결 여부를 YES/NO로 출력한다.(1<=i<=N)
(1번째 줄은 적군이 폭격을 시작하기 전 연결 여부이다.)
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 1点 | N,M<=3000 |
| #2 | 99点 | N,M<=200000 |
例題
4 3
1 2
2 3
3 4
3
4
1
2
YES
NO
YES
YES
タグ
出典
USACO 2016 US Open
ログインしないとコードを書けません。