RiseOJ – 소들의 모임

설명

전 세계의 소들이 대규모 모임을 위해 한자리에 모였다. 소는 $$N$$ 마리이고, 서로 친구인 소 쌍이 $$N-1$$ 개 있다. 모든 소는 친구 관계의 연쇄를 통해 다른 모든 소를 알고 있다.

소들은 즐거운 시간을 보냈지만, 이제 한 마리씩 떠나야 할 시간이 되었다. 소들은 적어도 두 마리가 남아 있는 동안에는 남아 있는 모든 소에게 남아 있는 친구가 있도록 하는 순서로 떠나고 싶어한다. 게다가 짐 보관 문제 때문에, 소 $$a_i$$ 가 소 $$b_i$$ 보다 먼저 떠나야 하는 소 쌍 $$(a_i, b_i)$$ 가 $$M$$ 개 있다. 소 $$a_i$$ 와 $$b_i$$ 는 친구일 수도 있고 아닐 수도 있다.

각 소에 대해, 그 소가 마지막으로 떠나는 소가 될 수 있는지 알아내도록 소들을 도와주자. 위 제약을 만족하며 소들이 떠나는 방법이 아예 존재하지 않을 수도 있다.

출제자: Dhruv Rohatgi

제약

출제자: Dhruv Rohatgi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$M$$ 이 주어진다.

$2 \leq i \leq N$ 번째 줄에는 각각 두 정수 $$x_i$$ 와 $$y_i$$ 가 주어지며 ( $1 \leq x_i, y_i \leq N$ , $x_i \neq y_i$ ), 이는 소 $$x_i$$ 와 $$y_i$$ 가 친구임을 나타낸다.

$N+1 \leq i \leq N+M$ 번째 줄에는 각각 두 정수 $$a_i$$ 와 $$b_i$$ 가 주어지며 ( $1 \leq a_i, b_i \leq N$ , $a_i \neq b_i$ ), 이는 소 $$a_i$$ 가 소 $$b_i$$ 보다 먼저 모임을 떠나야 함을 나타낸다.

$1 \leq N, M \leq 10^5$ 임이 보장된다. 배점의 $20\%$ 에 해당하는 테스트 케이스에서는 추가로 $N, M \leq 3000$ 임이 보장된다.

출력 형식

출력은 $$N$$ 개의 줄로 이루어지며, 각 줄에는 정수 $$d_i$$ 하나를 출력한다. 소 $$i$$ 가 마지막으로 떠날 수 있으면 $$d_i = 1$$ 이고, 그렇지 않으면 $$d_i = 0$$ 이다.

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:

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

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > December > Platinum

올림피아드 > USACO > 2018-2019 > December > Platinum

태그

JudgeUSACO

소들의 모임

평가 및 의견

풀이 제출