[USACO18DEC]The Cow Gathering P

题目描述

奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $ N $ 头奶牛, $ N-1 $ 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。 她们玩得很开心,但是现在到了她们应当离开的时间了,她们会一个接一个地离开。她们想要以某种顺序离开,使得只要至少还有两头奶牛尚未离开,所有尚未离开的奶牛都还有没有离开的朋友。此外,由于行李寄存的因素,有 $ M $ 对奶牛 $ (a_i,b_i) $ 必须满足奶牛 $ a_i $ 要比奶牛 $ b_i $ 先离开。注意奶牛 $ a_i $ 和奶牛 $ b_i $ 可能是朋友,也可能不是朋友。 帮助奶牛们求出,对于每一头奶牛,她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。

输入输出格式

输入格式


输入的第 $ 1 $ 行包含两个空格分隔的整数 $ N $ 和 $ M $ 。 输入的第 $ 2 \leq i \leq N $ 行,每行包含两个整数 $ x_i $ 和 $ y_i $ ,满足 $ 1 \leq x_i $ , $ y_i \leq N,xi \neq yi $ ,表示奶牛 $ x_i $ 和奶牛 $ y_i $ 是朋友关系。 输入的第 $ 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 $ 先离开聚会。 输入保证 $ 1 \leq N,M \leq 10^5 $ 。对于占总分 $ 20\% $ 的测试数据,保证 $ N,M \leq 3000 $ 。

输出格式


输出 $ N $ 行,每行包含一个整数 $ d_i $ ,如果奶牛 $ i $ 可以成为最后一头离开的奶牛,则 $ d_i=1 $ ,否则 $ d_i=0 $ 。

输入输出样例

输入样例 #1

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

输出样例 #1

0
0
1
1
1