坎格鲁斯普雷和袋鼠将军在游玩一款名叫“战争游戏”的游戏,在这款游戏中,坎格鲁斯普雷是进攻方,袋鼠将军是防守方。
游戏的地图可以抽象为一张有着 $n$ 个节点的树。初始时,防守方的人物在 $s$ 号节点。
游戏将会进行 $10^{100}$ 回合,在每一回合中,游戏的流程如下:
首先,进攻方会选择一个节点 $p$ ,作为轰炸中心,并对防守方进行“轰炸预告”,如果在回合结束时防守方所在的节点 $t$ 与轰炸中心 $p$ 的距离不超过轰炸半径 $r_1$ ,那么防守方的人物将会被炸死,此时游戏结束,进攻方获胜。之后 防守方可以操纵他的人物移动到与当前位置的距离不超过 $r_2$ 的节点上,然后回合结束。如果防守方的人物在回合结束时没被炸死,那么接着进行下一轮游戏,直到游戏轮次耗尽。若游戏轮次耗尽的时候防守方操纵的人物仍未死亡,那么防守方获胜,游戏结束。
作为袋鼠中的精英,坎格鲁斯普雷和袋鼠将军都是绝顶聪明的(即他们做出的操作都是当前盘面下的最优操作),那么在游戏结束时,谁将获胜?
输入第一行一个整数 $T$ ,表示测试数据组数。$(1≤T≤10^3 )$
每组测试数据,第一行四个整数 $n, s ,r_1, r_2(1≤n≤10^5, 1≤s,r_1,r_2 ≤n)$
之后 $(n−1)$ 行,每行两个整数 $u_i,v_i$,表示一条存在于树内的边。 $(1≤u_i,v_i ≤n)$
数据保证 $∑n≤2×10^6$ 。
对于每组测试数据,若坎格鲁斯普雷获胜,输出一行一个字符串 Kangaroo_Splay
;否则,输出一行一个字符串 General_Kangaroo
。每组测试数据的答案之间需换行。
2 5 3 2 3 1 2 2 3 3 4 3 5 5 1 1 3 1 2 2 3 3 4 3 5
\n · · · \n · \n · \n · \n · \n · · · \n · \n · \n · \n · \n
Kangaroo_Splay General_Kangaroo
\n \n