The Last Alpha Star

题目描述

你们是不是再也不想见到α星了，我保证，这是最后一次让你们见面了~
这样说吧，之前回到地球翻译单词神马的都弱爆了，真正想回去的方式只有一个，那就是从形状如同二叉树的α路上找到路径长度为恰好为L的路。我们暂且把α路比作是二叉树，那这里所指的路就是二叉树的根结点到叶子结点的一条路径。
α路路径长度L已经幸运地被Talus拿到了，那么接下来的任务就交给你了，帮助Talus去找回家的路。

输入

第一行是一个正整数t，表示测试数组组数(0<t<10)；
接下来有t组数据，每组数据第一行，为二叉树的广义表形式，长度不超过5000，二叉树的结点表示当前结点的路径长度，二叉树高度不超过12，即叶子节点数不超过2048 第二行是一个整数L，如题所述

输出

对于每组数组，首先输出一行"Case X:"，表示第X组数据 接下来，如果存在长度为L的路径，按照样例输出路径；如果有多条路径，那么依次按照二叉树从左到右的顺序输出。 如果不存在这样的路径，则输出"I am so sorry!"

输入样例

2
1(2(4,5),3(3,7))
7
1(2(4,5),3(6,7))
6

输出样例

Case 1:
1 2 4 
1 3 3 
Case 2:
I am so sorry!

Hint

二叉树