Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

【题目描述】

大家好啊,我是米浴树的道理,今天来点大家想看的东西啊。
你现在要和我在一棵米浴树上玩游戏。
一棵米浴树是由 $n$ 个点,$n - 1$ 条边组成的无色无向连通图,现在我们轮流对这棵树 染色,我用黑色,你用白色,我先开始。每次染色可以选择一个无色的结点染成自己手里 的颜色,直到所有无色结点都被染上某种颜色。如果最后有一个黑色的点周围不存在任 意白色节点,那我就赢了,否则算你赢。
给出这棵米浴树,在我们都使用最佳策略的情况下,谁一定会赢?

【输入格式】

从文件 tree.in 中读入数据。 第一行一个整数 $T$ 表示数据组数。 对于每组数据,第一行一个整数 $n$ 表示树的点数。 接下来 $n − 1$ 行,每行两个整数 $u_i , v_i$ 表示存在一条连接点 $u_i$ 和点 $v_i$ 的边,保证给 出的是一棵树。

【输出格式】

输出到文件 tree.out 中。 对于每组数据,如果我(先手)必胜,输出一行 shudedaoli,否则输出一行 amiyu

【样例 1 输入】

1
4
1 2
2 3
2 4

【样例 1 输出】

shudedaoli

【测试点约束】

对于所有测试点,$1 ≤ T ≤ 10,2 ≤ n ≤ 10^5,1 ≤ u_i , v_i ≤ n$,保证给出的是一棵树。