题目描述

题目来自 USACO 2018 December Contest, Platinum Problem 3. The Cow Gathering

有 $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$。

样例

输入

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

输出

0
0
1
1
1