#PU866. USACO 2018 December Contest, Platinum — Problem 3. The Cow Gathering

    ID: 1266 传统题 文件IO:gathering 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec18来源:usaco.orgscoring:equal_test_cases拓扑排序

USACO 2018 December Contest, Platinum — Problem 3. The Cow Gathering

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 N−1N-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)(a_i, b_i) such that cow aia_i must leave before cow bib_i. Note that the cows aia_i and bib_i 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

输入格式

Line 11 contains two space-separated integers NN and MM. Lines 2≤i≤N2 \leq i \leq N each contain two integers xix_i and yiy_i with 1≤xi,yi≤N1 \leq x_i, y_i \leq N and xi≠yix_i \neq y_i indicating that cows xix_i and yiy_i are friends. Lines N+1≤i≤N+MN+1 \leq i \leq N+M each contain two integers aia_i and bib_i with 1≤ai,bi≤N1 \leq a_i, b_i \leq N and ai≠bia_i \neq b_i indicating that cow aia_i must leave the gathering before cow bib_i. It is guaranteed that 1≤N,M≤1051 \leq N, M \leq 10^5. In test cases worth 20%20\% of the points, it is further guaranteed that N,M≤3000N, M \leq 3000.

输出格式

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

数据范围

(见题面原文)

样例

样例 1

5 1
1 2
2 3
3 4
4 5
2 4
0
0
1
1
1
Problem credits: Dhruv Rohatgi