소들의 모임

소 $N$마리가 있고, 서로 친구인 소 쌍은 $N-1$개이다. 모든 소는 친구 관계를 거쳐 다른 모든 소와 연결되어 있다.

모임은 즐거웠지만, 이제 소들이 한 마리씩 떠날 때가 되었다. 소들은 남은 소가 두 마리 이상인 동안 남아 있는 모든 소에게 남아 있는 친구가 한 명 이상 있도록 떠나는 순서를 정하려고 한다. 또한 짐 보관 문제로 인해 소 $a_i$가 소 $b_i$보다 먼저 떠나야 하는 쌍 $(a_i, b_i)$가 $M$개 있다. 소 $a_i$와 $b_i$는 친구일 수도 있고 아닐 수도 있다.

각 소에 대해, 그 소가 마지막으로 떠날 수 있는지 알아내라. 위의 조건을 모두 만족하는 떠나는 순서가 없을 수도 있다.

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

$2 ≤ i ≤ N$인 각 줄에는 두 정수 $x_i$와 $y_i$가 주어진다. $1 ≤ x_i, y_i ≤ N$이고 $x_i ≠ y_i$이며, 소 $x_i$와 $y_i$가 친구라는 뜻이다.

$N+1 ≤ i ≤ N+M$인 각 줄에는 두 정수 $a_i$와 $b_i$가 주어진다. $1 ≤ a_i, b_i ≤ N$이고 $a_i ≠ b_i$이며, 소 $a_i$가 모임을 떠나기 전에 소 $b_i$가 먼저 떠나면 안 된다는 뜻이다. 즉 소 $a_i$가 소 $b_i$보다 먼저 떠나야 한다.

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

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