The Cow Gathering

题目描述

奶牛们从世界各地聚集在一起参加一场盛会。有 $N$ 头奶牛，以及 $N-1$ 对互为朋友的奶牛。每头奶牛都可以通过某条由友谊关系构成的链认识到其他所有奶牛。\n她们玩得很开心，但现在到了分别的时候，奶牛将一头一头地离开。她们希望按照某种顺序离开，使得只要还至少剩下两头奶牛，每一头仍留下的奶牛都至少有一位仍留下的朋友。此外，由于行李存放的问题，存在 $M$ 对奶牛 $(a_i, b_i)$，要求奶牛 $a_i$ 必须在奶牛 $b_i$ 之前离开。注意，奶牛 $a_i$ 和 $b_i$ 可能是朋友，也可能不是。\n请帮助奶牛们判断：对于每一头奶牛，她是否可能成为最后离开的一头。也可能根本不存在满足上述约束的离开方式。

输入格式

第 $1$ 行包含两个用空格分隔的整数 $N$ 和 $M$。\n第 $2 \leq i \leq N$ 行每行包含两个整数 $x_i$ 和 $y_i$，满足 $1 \leq x_i, y_i \leq N$ 且 $x_i \neq y_i$，表示奶牛 $x_i$ 与奶牛 $y_i$ 是朋友。\n第 $N+1 \leq i \leq N+M$ 行每行包含两个整数 $a_i$ 和 $b_i$，满足 $1 \leq a_i, b_i \leq N$ 且 $a_i \neq b_i$，表示奶牛 $a_i$ 必须在奶牛 $b_i$ 之前离开聚会。

输出格式

输出应包含 $N$ 行，每行一个整数 $d_i$，使得当奶牛 $i$ 可能成为最后离开的一头时 $d_i = 1$，否则 $d_i = 0$。

5 1\n1 2\n2 3\n3 4\n4 5\n2 4

0\n0\n1\n1\n1

提示

保证 $1 \leq N, M \leq 10^5$。在占总分 $20\%$ 的测试点中，额外保证 $N, M \leq 3000$。\n题目来源：Dhruv Rohatgi

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum