The Cow Gathering
The Cow Gathering
Cows have assembled from around the world for a massive gathering. There are n cows, and n − 1 pairs of cows who are friends with each other. Every cow knows every other cow through some chain of friendships.
They had great fun, but the time has come for them to leave, one by one. They want to leave in some order such that as long as there are still at least two cows left, every remaining cow has a remaining friend. Furthermore, due to issues with luggage storage, there are m pairs of cows (ai
, bi
) such that cow ai
must leave before cow bi
. Note that the cows ai
and bi
may or may not be friends.
Help the cows figure out, for each cow, whether she could be the last cow to leave. It may be that there is no way for the cows to leave satisfying the above constraints.
Input
Line 1 contains two integers n and m (1 ≤ n, m ≤ 105
).
Lines 2 ≤ i ≤ n each contain two integers xi
and yi
with 1 ≤ xi
, yi
≤ n and xi
≠ yi
indicating that cows xi
and yi
are friends.
Lines n + 1 ≤ i ≤ n + m each contain two integers ai
and bi
with 1 ≤ ai
, bi
≤ n and ai
≠ bi
indicating that cow ai
must leave the gathering before cow bi
.
Output
The output should consist of n lines, with one integer di
on each line such that di
= 1 if cow i could be the last to leave, and di
= 0 otherwise.
5 1 1 2 2 3 3 4 4 5 2 4
0 0 1 1 1