[PA2014]Bazarek

时间限制:10s      空间限制:256MB

题目描述

一棵N个点的有根树,每个非叶子点有奇数个儿子。
每个叶子节点有三种状态,要么是红色,要么是蓝色,要么没有染色。
小红和小蓝在上面玩游戏,轮流操作,小红先手。每次操作者可以先一个未被染色的叶子染上自己的颜色。当所有叶子都有颜色后,整个树的所有非叶子节点会按逆BFS序确定颜色,即每个点变成它儿子中出现次数更多的那一种颜色。最终根节点的颜色代表胜利一方,求先手是否必胜,如果先手必胜,还要输出先手第一步可以选择叶子使得自己必胜。
N<=1000000


输入格式


输出格式


样例输入

4
4 2 1 3
3
2
3
4

样例输出

7
9
-1

提示

没有写明提示


题目来源

没有写明来源