{"raw_statement":[{"iden":"background","content":"在小树上坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。\n\n为了打造一个完美的 E 国，他需要明辨是非，走向正义。\n\n但是，他似乎有些太理想了。有时并没有一个完美的准则。是黑是白，谁能分辨？"},{"iden":"statement","content":"给定一棵 $n$ 个结点，以 $1$ 为根的树，定义一个结点的深度 $d_i$ 表示它到根结点的简单路径上的结点个数。\n\n你需要给每个结点黑白染色，满足黑色结点的深度和等于白色结点的深度和。设 $c_i = \\{0, 1\\}$ 分别代表编号为 $i$ 的结点为黑色或白色，那么这即 $\\displaystyle\\sum_{c_i=0}d_i=\\sum_{c_i=1}d_i$。\n\n若无解，仅输出一行一个整数 $-1$。"},{"iden":"input","content":"第一行一个正整数 $n$。\n\n接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$，表示树上编号为 $u_i$ 的结点与编号为 $v_i$ 的结点之间有一条边。保证给出的边不重复。"},{"iden":"output","content":"若有解，则输出一行 $n$ 个数 $c_1\\dots c_n$。\n\n若无解，仅输出一行一个整数 $-1$。\n\n**本题开启 Special Judge，只要你的方案满足条件或正确判断无解即可拿到本测试点的分数。**"},{"iden":"note","content":"### 样例解释\n\n对于第一组数据，每个结点的深度分别是 $d=[1,2,2,3,3,3]$。黑色结点的深度和为 $d_1+d_5+d_6=1+3+3=7$，白色结点的深度和为 $d_2+d_3+d_4=2+2+3=7$。它们相等，所以样例输出是正确的。可能的正确输出包括但不限于样例输出、`0 1 1 0 0 1`，`1 0 0 1 0 1` 等。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n| $\\rm Subtask$ | 分值 | $n\\le $ | 特殊性质 |\n| :-----------: | :--: | :-----: | :------: |\n| $0$ | $5$ | $20$ | / |\n| $1$ | $15$ | $500$ | / |\n| $2$ | $20$ | $5\\times 10^3$ | / |\n| $3$ | $10$ | / | $n$ 为偶数 |\n| $4$ | $5$ | / | 树为菊花图（不保证根为菊花中心） |\n| $5$ | $5$ | / | 树为一条链（不保证根为链的端点） |\n| $6$ | $40$ | / | / |\n\n斜杠表示这一栏无特殊限制。\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^6$，$1\\le u_i,v_i\\le n$，输入数据构成一棵树。"}],"translated_statement":null,"sample_group":[["6\n1 2\n1 3\n2 4\n2 5\n2 6","0 1 1 1 0 0"],["5\n1 2\n1 3\n2 4\n2 5","-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}