练习专区

树可以用一维数组t[]来存储。让第i个结点的t[i]存储它前一个结点的序号。如下图： 我们可以记t[1]=0，t[3]=1，t[6]=1，t[2]=1，t[4]=3，t[5]=6，t[7]=6，t[8]=6。这样可以从某个结点一直访问到根结点。 你的任务是给你一棵树，请你输出从根结点到每个结点的路径。

输入有若干个案例，每个案例第一个数是一个正整数n，表示树枝的个数，然后有n行，每行两个数i，j，表示从i到j有一条路。n=0表示结束。

先输出“Case id:”，再按结点的序号输出从根结点开始的路径。格式见样例。

7
1 3
1 6
1 2
3 4
6 5
6 7
6 8
0

Case 1:
1:1
2:1 2
3:1 3
4:1 3 4
5:1 6 5
6:1 6
7:1 6 7
8:1 6 8