来自世界各地的奶牛们聚集在一起参加一场盛大的聚会。共有 $N$ 头奶牛，其中有 $N-1$ 对奶牛互为朋友。每头奶牛都能通过某种友谊链与其他所有奶牛建立联系。

它们玩得很开心，但现在到了逐一离开的时候了。它们希望以某种顺序离开，使得只要剩下的奶牛至少还有两头，每一头留下的奶牛都至少还有一个留下的朋友。此外，由于行李存放的问题，有 $M$ 对奶牛 $(a_i, b_i)$，其中奶牛 $a_i$ 必须在奶牛 $b_i$ 之前离开。注意，奶牛 $a_i$ 和 $b_i$ 不一定是朋友。

请帮助奶牛们确定，对于每一头奶牛，它是否可能是最后一头离开的奶牛。可能不存在满足上述所有约束条件的离开顺序。

输入格式

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

第 $2$ 行到第 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq N$ 且 $x_i \neq y_i$），表示奶牛 $x_i$ 和 $y_i$ 是朋友。

第 $N+1$ 行到第 $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