问题1224--下围棋

1224: 下围棋

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

小姜在和miaoyao下围棋,由于在19X19的棋盘上面小姜总是输给miaoyao,于是他们是在一个有根树(根为1号节点,编号1-n)上面下围棋,围棋的规则也和我们日常说的规则不同。


规则如下:小姜和miaoyao轮流下棋,小姜执黑miaoyao执白,每次落子在一个树上面的合法节点,一个节点是合法节点仅当满足
1.该节点之前没有棋子
2.该节点不能是根节点(1号节点)
3.该节点到根的路径上面没有其他棋子


当某一方无法落子的时候,这一方输掉游戏。显然,如果场面上面存在合法的节点,轮到这个人时他必须落子。(不能pass)

输入

第一行是一个数字,代表数据组数
每一组数据有一行正整数n,代表节点个数
接下来n-1行,每行两个数字,代表一条边的起点终点
保证输入是一个树

输出

每组数据输出一行
如果小姜必败,输出“”YES”
否则输出“NO”


注意换行x


样例输入 Copy

2
3
1 2
1 3
4
1 2
1 3
3 4

样例输出 Copy

YES
NO

提示

\( \sum{n}<=1e5\)