描述

有一个棋子放在一颗有根树的根上。你和算卦先生轮流把这个棋子向所在点的其中一个儿子移动（只能移动到儿子）。不能再移动就算失败（即棋子所在节点没有儿子）。
算卦先生来问你，如果你先手，你是否有必胜策略？

Input

第一行一个数$T$，表示有$T$组数据。接下去每组数据的第一行有两个数$n,r$，表示树有$n$个节点，其中$r$为根节点编（从1开始编号）。
接下去$n−1$行每行两个数字$u,v$，表示点$u$和$v$之间有一条边。
$1≤T≤10$
$1≤n≤10000$
$1≤r≤n$

Output

每组数据输出一行，”Gen”表示先手有必胜策略，”Dui”表示没有。

Examples

intput
1
2
3
4
5
6
7
8
9
2
3 1
1 2
2 3
5 4
1 2
1 3
3 4
4 5
output
1
2
Dui
Gen

思路

从叶子节点往根节点推，面对叶子节点时显然是必胜态。

面对每一个节点时，如果它的子节点全都是必胜态，那么这个节点就是必败态，只要它的子节点中有一个必败态，那这个节点就是必胜态（因为可以转移成下一个人面对必败态）。

dfs即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e4+5;

struct node{int To,Next;}Edge[N*2];     //链式前向星存图
int cnt=0,Begin[N];

void add(int a,int b){
    Edge[cnt]=(node){b,Begin[a]};
    Begin[a]=cnt++;
}

bool dfs(int x,int f){          //必胜态返回true  必败返回false
    for(int i=Begin[x];~i;i=Edge[i].Next){
        if(Edge[i].To==f) continue;
        if(!dfs(Edge[i].To,x)) return true;     //如果子节点出现必败态，这个节点就是必胜态
    }
    return false;           //子节点全是必胜态
}

int main()
{
    int T,n,root,x,y;
    scanf("%d",&T);
    while(T--){
        cnt=0;
        CRL(Begin,-1);
        scanf("%d%d",&n,&root);
        rep(i,1,n){
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        puts(dfs(root,-2)? "Gen":"Dui");
    }
    return 0;
}