爱丽丝和鲍勃是两个在森林里砍伐树木的偷猎者。
森林是零个或更多树的集合。树是没有环的连通图。有根树有一个特殊的顶点,称为根。节点 $$$v$$$ 的父节点是从 $$$v$$$ 到根的最短路径上的下一个顶点。顶点 $$$v$$$ 的子节点是以 $$$v$$$ 为父节点的所有节点。如果一个顶点没有子节点,那么它就是一个叶子。
在这个问题中,我们将顶点的深度定义为从该顶点到根的简单路径上的顶点数。树的等级是其叶子之间的最小深度。
最初有一片有根的树木森林。爱丽丝和鲍勃在这片森林里玩游戏。他们轮流玩,爱丽丝先玩。在回合开始时,玩家从森林中选择一棵树。然后玩家选择一个正的切割深度,该深度不应超过所选树的等级。然后玩家删除深度小于或等于切割深度的树的所有顶点。树的所有其他顶点形成一组有根树,根是切割前深度最小的顶点。所有这些树都包含在游戏森林中,游戏继续进行。
如果玩家在行动开始时森林是空的,那么他就输了。
如果两个玩家都发挥最佳,您将确定 Alice 是否赢得了游戏。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — 初始森林中的顶点总数。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n$$$) — 森林的描述。如果$$$p_i = 0$$$,则第$$$i$$$个顶点是树的根,否则$$$p_i$$$是顶点$$$i$$$的父节点。保证 $$$p$$$ 定义了正确的有根树森林。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Alice 获胜,则打印“YES”(不带引号),否则打印“NO”(不带引号)。您可以以任何大小写(大写或小写)打印每个字母。
示例
输入 #1
4 4 0 1 0 3 7 0 1 2 0 4 5 6 4 0 1 1 2 7 0 1 1 2 2 3 3
输出 #1
NO YES NO YES
注意
在第一个测试用例中,Bob 采用对称策略,因此 Alice 无法获胜。
在第二个测试用例中,Alice 可以选择第二棵树和切割深度 $$$1$$$ 来获得她具有对称策略的森林。
在第三个测试用例中,唯一的树的等级是 $$$2$$$,Alice 的两种可能的移动都会导致损失。鲍勃要么可以用对称策略为自己创造森林,要么清理森林。
在第四个测试用例中,所有叶子都具有相同的深度,因此爱丽丝可以一步清除森林。