问题1109--张老师和石头的battle

1109: 张老师和石头的battle

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

题目描述

由于临近比赛,张老师和石头的题目还剩一道没出完,他们因为由谁出这最后一道,打起来了。他们找到了新格尔公司的天才程序员菜哭武,让菜哭武来决定谁来出最后一道题。于是菜哭武想到这样一个游戏,在一棵多叉树上面,让张老师和石头任意选择一个节点,每次让张老师先走,每次走到当前节点的父亲节点上,石头后走。当一个人走到了另一个人的祖先节点上,就算获胜,不用出这最后一道题。

输入

第一行,一个正整数t(0<t<10),表示数据组数。
每组第一行包含两个数N,M(N,M≤100,000),N表示树的节点数,M表示询问数,节点的编号为1到N。
接下来N−1行,每行2个整数A,B(1≤A,B≤N),表示编号为A的节点是编号为B的节点的父亲。
接下来M行,每行有2个数,表示Teacher和Stone的初始位置的编号X,Y(1≤X,Y≤N,X≠Y),Teacher总是先移动。

输出

对于每次数据,输出M+1行。

第一行输出Case #t:,t表示第t组数据

第二到第M+1行输出每组询问获胜者的名字(顺序与输入顺序相同)。

样例输入 Copy

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

样例输出 Copy

Case #1:
Teacher
Case #2:
Stone
Teacher

来源/分类