树是一个连通的非循环图。假设给你一棵由 n 个顶点组成的树。如果从树中删除该顶点后出现的每个连通分量的大小不超过 $$\frac{\pi}{2}$$,则该树的顶点称为质心。
给定一棵大小为 n 的树,并且只能执行一个边替换。边替换是从树中删除一条边(不删除关联顶点)并插入一条新边(不添加新顶点)的操作,使得图仍然是一棵树。对于每个顶点,您必须确定是否可以通过执行不超过一条边替换来使其成为质心。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 400 000) — 树中的顶点数。接下来的 n - 1 行中的每一行都包含一对顶点索引 ui 和 vi (1 ≤ ui, vi ≤ n) - 相应边的端点。
输出
打印 n 个整数。如果第 i 个顶点可以通过替换不超过一条边作为质心,则它们中的第 i 个应等于 1,否则应等于 0。
示例
输入 #1
3 1 2 2 3
输出 #1
1 1 1
输入 #2
5 1 2 1 3 1 4 1 5
输出 #2
1 0 0 0 0
注意
在第一个样本中,每个顶点都可以作为质心。例如,为了将顶点 1 转变为质心,必须将边 (2, 3) 替换为边 (1, 3)。