USACO 2018 December Contest Platinum Problem 3 The Cow Gathering

Cows have assembled from around the world for a massive gathering. There are NN cows, and N1N−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 MM pairs of cows (ai,bi)(ai,bi) such that cow aiai must leave before cow bibi. Note that the cows aiai and bibi 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.


Line 11 contains two space-separated integers NN and MM.Lines 2iN2≤i≤N each contain two integers xixi and yiyi with 1xi,yiN1≤xi,yi≤N and xiyixi≠yi indicating that cows xixi and yiyi are friends.

Lines N+1iN+MN+1≤i≤N+M each contain two integers aiai and bibi with 1ai,biN1≤ai,bi≤N and aibiai≠bi indicating that cow aiai must leave the gathering before cow bibi.

It is guaranteed that 1N,M1051≤N,M≤105. In test cases worth 20%20% of the points, it is further guaranteed that N,M3000N,M≤3000.

OUTPUT FORMAT (file gathering.out):

The output should consist of NN lines, with one integer didi on each line such that di=1di=1 if cow ii could be the last to leave, and di=0di=0 otherwise.


5 1
1 2
2 3
3 4
4 5
2 4



Problem credits: Dhruv Rohatgi

USACO 2018 December Contest Platinum Problem 3 The Cow Gathering题解(翰林学院提供,仅供参考)