P5157 [USACO18DEC] The Cow Gathering P

Cows from all over the world have gathered for a big party. There are a total of $N$ cows, and $N-1$ pairs of cows are friends. Each cow can get to know every other cow through some chain of friendships. They have had a great time, but now it is time for them to leave, one by one. They want to leave in some order such that, as long as at least two cows have not left yet, every remaining cow still has at least one friend who has not left. In addition, due to baggage storage constraints, there are $M$ pairs of cows $(a_i,b_i)$ that must satisfy that cow $a_i$ leaves before cow $b_i$. Note that cows $a_i$ and $b_i$ may or may not be friends. Help the cows determine, for each cow, whether she can be the last cow to leave. It is possible that there is no leaving order that satisfies the above requirements.

The first line of input contains two space-separated integers $N$ and $M$. The following $N-1$ lines (for $2 \leq i \leq N$) each contain two integers $x_i$ and $y_i$, satisfying $1 \leq x_i$, $y_i \leq N, xi \neq yi$, indicating that cows $x_i$ and $y_i$ are friends. The following $M$ lines (for $N+1 \leq i \leq N+M$) each contain two integers $a_i$ and $b_i$, satisfying $1 \leq a_i,b_i \leq N$ and $a_i \neq b_i$, indicating that cow $a_i$ must leave the party before cow $b_i$. The input guarantees $1 \leq N,M \leq 10^5$. For the testdata worth $20\%$ of the total score, it is guaranteed that $N,M \leq 3000$.

Output $N$ lines. Each line contains an integer $d_i$. If cow $i$ can be the last cow to leave, then $d_i=1$; otherwise, $d_i=0$.

Translated by ChatGPT 5