문제
N개의 정점으로 이루어진 트리가 있다.
이 트리의 정점들을 하나씩 지워보려고 한다.
그러나 트리가 둘로 쪼개지면 어수선하기 때문에, 한 정점이 없어지더라도 트리가 하나로 유지하도록 하려고 한다.
어떤 한 정점은 다른 정점보다 먼저 없어져야 한다. 이런 우선순위 정점 관계가 총 M개 있다.
각 N개의 정점에 있어서, 그게 제일 마지막으로 지워지는 정점일 수 있는지 없는지 검사하는 프로그램을 작성하라.
입력
첫 줄에 N과 M이 공백을 사이에 두고 주어진다.(1 <= N <= 100,000, 1 <= M <= 100,000)
다음 N-1줄엔 x y가 입력되며, 이는 x와 y가 서로 연결되어 있다는 의미이다.
다음 M줄에 a b가 입력되며, 이는 a가 b보다 먼저 사라져야 하는 정점이라는 의미이다. 1 <= a,b,x,y <= N이다.
20%의 입력 데이터에 있어서, N,M <= 3,000임을 보장한다.
출력
N줄에 걸쳐서 각 줄에 해당하는 정점이 마지막으로 지워질 수 있으면 1, 없으면 0을 출력한다.
예제
5 1
1 2
2 3
3 4
4 5
2 4
0
0
1
1
1
태그
출처
USACO 2018 December, Platinum 3
로그인해야 코드를 작성할 수 있어요.