A6417 | 「USACO 2018.12 Platinum」The Cow Gathering

**题目来自 [USACO 2018 December Contest, Platinum](http://usaco.org/index.php?page=dec18results) Problem 3. [The Cow Gathering](http://usaco.org/index.php?page=viewproblem2&cpid=866)**

奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $N$ 头奶牛，$N-1$ 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。

她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外，由于行李寄存的因素，有 $M$ 对奶牛 $(a_i,b_i)$ 必须满足奶牛 $a_i$ 要比奶牛 $b_i$ 先离开。注意奶牛 $a_i$ 和奶牛 $b_i$ 可能是朋友，也可能不是朋友。

帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

输入的第 $2\le i\le N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，满足 $1\le x_i,y_i\le N$，$x_i\neq y_i$，表示奶牛 $x_i$ 和奶牛 $y_i$ 是朋友关系。

输入的第 $N+1\le i\le N+M$ 行，每行包含两个整数 $a_i$ 和 $b_i$，满足 $1\le a_i,b_i\le N$，$a_i\neq b_i$，表示奶牛 $a_i$ 必须比奶牛 $b_i$ 先离开聚会。

输入保证 $1\le N,M\le 10^5$。对于占总分 $20\%$ 的测试数据，保证 $N,M\le 3000$。

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