题目描述

格列布和科利亚在一个树上（无环连通图）玩游戏。他们轮流进行操作，格列布先行。在第一个回合中，每个玩家将自己的棋子放置在树的任意顶点上，但科利亚不能将自己的棋子放在格列布已放置棋子的顶点。

在接下来的每个回合中，玩家将自己的棋子从当前顶点通过某条边移动到相邻的顶点。玩家不能将棋子移动到曾经或当前有任一棋子停留过的顶点。无法进行移动的玩家输掉游戏。

请确定在双方玩家都采用最优策略的情况下，格列布是否能赢得游戏。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 100000)$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(2 \leq n \leq 100000)$，表示树中顶点的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(1 \leq a_i, b_i \leq n)$，表示连接两个顶点的边。保证输入的图是一棵树。

所有测试用例中 $n$ 的总和不超过 $100000$。

输出格式

对于每个测试用例，如果格列布能赢得游戏，则在新的一行中输出 Yes；否则输出 No。

2
3
1 2
2 3
8
1 3
3 5
3 7
1 6
1 4
4 2
5 8

Yes
No

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。