Alice and Bob are playing a game on a tree $$$T$$$ whose root is $$$1$$$. $$$T$$$ has $$$n$$$ vertices and $$$n-1$$$ edges, each vertex has an attribute $$$a \in \{1,2,3\}$$$. If $$$a=1$$$, a person on this vertex $$$v$$$ must jump to the parent of $$$v$$$, i.e., $$$v->parent$$$. If $$$a=2$$$, a person on this vertex $$$v$$$ must jump to $$$v$$$'s grandparent, i.e., $$$v->parent->parent$$$. If $$$a=3$$$, a person on this vertex can either jump to $$$v->parent$$$ or $$$v->parent->parent$$$. Alice starts the first. If somebody cannot make a move, she/he loses the game. For example, if Alice stands on a child of the root and this child has attribute $$$2$$$, then Alice loses as this child does not have a grandparent. Similarly if Bob stands on the root, he will lose as he cannot move no matter what the attribute of the root is.

Input contains $$$n+1$$$ lines.

The first line contains a single integer $$$n$$$, which is the number of vertices.

The