题目描述

奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $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$ 。

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

0
0
1
1
1