Equal Depth Sum Partition

Given a tree with (n) nodes rooted at node (1), where the depth (d_i) of a node (i) is defined as the number of nodes on the simple path from the root to (i), assign a color to each node (black or white) such that the sum of depths of the black nodes equals the sum of depths of the white nodes. Formally, let (c_i \in {0,1}) denote the color of node (i) (with 0 for black and 1 for white), then the condition to satisfy is [ \sum_{i: c_i=0} d_i = \sum_{i: c_i=1} d_i. ] If no valid coloring exists, output a single line containing (-1).

Input Format: The first line contains an integer (n) ((1 \le n \le 40)). For (n>1), the second line contains (n-1) space-separated integers where the (i)th integer (for (2 \le i \le n)) denotes the parent of node (i). For (n=1), the second line is omitted.

inputFormat

The input consists of one or two lines. The first line contains a single integer (n) representing the number of nodes. If (n > 1), the second line contains (n-1) space-separated integers; the (i)th integer gives the parent of node (i+1).

outputFormat

If a valid coloring exists, output a single line containing (n) space-separated integers. The (i)th integer should be 0 if node (i) is colored black and 1 if it is colored white. If no valid coloring exists, output a single line with (-1).

sample

4
1 1 2

0 1 1 0