Problem 1109. -- 张老师和石头的battle

1109: 张老师和石头的battle

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 210  Solved: 41
[Submit][Status][Web Board]

Description

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

Input

第一行,一个正整数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总是先移动。

Output

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

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

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

Sample Input

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

Sample Output

Case #1:
Teacher
Case #2:
Stone
Teacher

HINT

Source

[Submit][Status]