提示: 欢迎访问OurACM平台。
Problem 2207 以撒的结合

Accept: 75    Submit: 242
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小茗同学最近在认真地准备比赛,所以经常玩以撒的结合。

《以撒的结合》是一款由Edmund McMillen,Florian Himsl 开发,并由Edmund McMillen最早于2011年09月29日发行的一款2D平面角色扮演、动作冒险类的独立游戏。游戏的角色将在有着能够提升能力的道具与特殊技能的半RPG世界中闯荡。

——来自百度百科

小茗同学在打BOSS前,费掉了很多HP。在地图的一些房间里有补充HP的红心,然而小茗同学受到了看不见地图的诅咒。凭借不知道哪里来的记忆,小茗同学记得某个有红心的房间在房间A与房间B的路上的第K个房间里。为了简化问题,我们把地图看成一棵树。小茗同学想知道A到B的第K个房间号为多少,由于小茗同学很累,所以现在这个任务交给你了。

Input

第一行是一个整数T(T<=10),表示有T组测试数据。

每组数据的第一行为两个整数n m(0<n<=1000,0<m<=n*n),分别表示房间个数和询问次数。

接下来n-1行,每行两个整数u v(0<u、v<=n,且u≠v),表示地图上房间u和房间v有一条路径。

最后是m行,每行三个整数u v k,表示询问房间u到房间v的路径上的第k个房间。

输入数据保证合法,即k不超过u、v的最短距离。

Output

对于每组数据,首先第一行先输出“Case #x:“ ,其中x是从1开始,表示数据组号,接下来m行,每行输出相应的房间号。

Sample Input

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

Sample Output

Case #1: 3 3 5

Source

FOJ有奖月赛-2015年11月

Submit  Back  Status  Discuss