题目描述

定义树的重心：一个点是树的重心，当且仅当删去这个点后产生的所有连通块的节点数不超过原树节点数的 $\frac 1 2$。也就是说，如果原树有 $n$ 个节点，产生的任意连通块节点数不超过 $\lfloor\frac n 2\rfloor$。

LCT（Link-Cut Tree）：一种用于解决动态树问题的数据结构，支持两种操作：删去一条边（cut），加入一条连接两个尚未连通的点的边（link）。

你有一棵 $n$ 个节点的树，现在你要交替进行 $k$ 次 cut 和 $k$ 次 link 操作，可以对任意一条边进行操作。你需要解决的问题是：对于每个节点，$k$ 次操作结束后它是否有可能成为新树的重心。为了重心的唯一性，保证 $n$ 是奇数。

输入格式

第一行两个整数 $n$ , $k$，表示树的节点数和操作次数。 第二行到第 $n$ 行，第 $i+1$ 行两个整数 $u_i$ 和 $v_i$，表示初始时有一条连接 $u_i$ 和 $v_i$ 的边。

输出格式

输出共 $n$ 行。第 $i$ 行一个整数，0 表示第 $i$ 个节点不可能成为重心，1 表示第 $i$ 个节点可能成为重心。

样例

input

7 2
1 2
1 3
1 4
1 5
5 6
6 7

output

1
1
1
1
1
1
1

让 5 成为重心的一种方法：断开 $ (1,2) $，连接 $ (5,2) $，断开 $ (5,2) $，连接 $ (5,2) $。 让 6 成为重心的一种方法：断开 $ (1,2) $，连接 $ (6,2) $，断开 $ (1,3) $，连接 $ (6,3) $。 让 7 成为重心的一种方法：断开 $ (1,2) $，连接 $ (7,2) $，断开 $ (5,1) $，连接 $ (7,1) $。

数据范围与提示

注

与「JZOJ 5028」跳蚤王国（来源：毛啸）类似。