zoj1011
老师让做zoj1011上的题，苦于那里都是英文题目，有的大牛用在线翻译站点翻译了一下，让我们更深刻地感觉到“翻译即背叛”……尤其是用电脑翻译……………………
为了使背叛的程度尽可能地减小，咱小菜来人工翻译了一遍，应该还是能读通的把，不通顺或者对题意不明的童鞋，可以留言或者与我qq联系。
我翻译的不是试题，是寂寞…………
非判断性树型自动机（NTA）是一种由多个树型结构组成的设备。每种设备在自己的一种特定的规则下运行，依据这种规则设备中的每个树型结构可以产生一系列的信号，这些信号可以组成一个信号系统。在这个系统里面，其中一个信号叫做“开始信号”，还有一些信号叫做“可接受信号”，其他的信号叫做“辅助信号”。一对“可接受信号”可以组成一个“可接受对”。
我们现在说的这些树都是二叉树，即所有的非叶子节点都有两个儿子，每个节点都有一种叫做“信号传输管理器”的装置，当这个节点接受到一个信号的时候，信号接触到这个节点的信号传输管理器，信号传输管理器产生一系列的信号对，然后节点随机地选择出其中的一对信号并将其传送给节点的左右儿子，信号对中第一个送到左儿子，第二个送给右儿子。
非判断性树型自动机的工作全过程如下所述：
设备首先向根节点发送一个信号，接着根据根节点的信号传送管理器的内建规则在规则允许的范围内随机地生成一对信号，并把第一个信号送给左儿子，第二个送给右儿子。之后每一个信号都分别生成两个信号，这样的传送路线一直传送到叶子节点。
如果一个信号达到了叶子节点并且叶子节点产生了两个可接受信号，我们就说这个叶子节点是shakable leaf，如果所有的叶子节点都是shakable leave，这次信息传递就是一次合法的信息传递，如果一个树型结构存在这么一种合法的传输，那么这个树型结构和它的信号传输物质就是合法的，如果所有传输都是不合法传输，这棵树就是不合法树。
简而言之，我们用一连串的连续小些字母'a','b','c'……来表示那些信号传输控制器，这个机器所传输的信号是一些连续的数字0,1,2……，第一种信号0永远是其实信号。一个四信号非判断性树型自动机传送的信号是0,1,2,3。可接受信号是可传送信号序列的后面几个信号，比如说，如果一台四信号非判断性树型自动机有两个可接受信号，那么这两个信号就是2,3，信号传送法则基于一个信号传送方式表，横向表头是信号传输控制器a,b,c，纵向表头是接受到的信号0,1,2,3，一个传送法则的样例如下所示：
T a b c
0 (1,2) (2,1) (1,0)
1 (2,2) (0,2),(1,0) (3,2)
2 (2,2) (2,3) (1,2)
3 (1,2) (2,1) (3,2)
在这个信号传送方式表里面，一些信号传送管理器是确定性的，其他的是不确定性的，在上表里面，当信号1遇到信号传送管理器b的时候，产生的信号对是不确定的。
你的任务就是写一个程序来判断一个拥有特定信号传输管理器的树性结构是不是合法的。
输入：
一个输入文件包含几个情景，每个情景描述了一个信号传送法则，每个信号传送法则适用于一个情景。每个情景的第一行包含三个整数n,m,k。n表示这是一个n信号非确定性树型自动机；m表示这个设备的所有信号里面后m个是合法信号；k表示这个设备拥有的信号传输管理器的种数。（这三个参数也是只对当前情景有效）接下来的n*k行是以行优先方式输出的信号传送方式表，每个信号－－信号传送管理器组合占一行，每行两个数字一组，每组表示一种可能的信号转换方式。
接下来是对树的结构的描述，每个树都有一个深度值L，表示树的深度为（L＋1）。接下来的L+1行都是对数结构的描述，一行描述一层节点，字母间用空格分隔，根层是第0层。树中的空节点用＊表示。如果一棵树的层数为－1，那就表明这种情景结束了。
如果一个情景的nmk三参数都是0，那么说明这个输入文件结束了。
注意：
每个情景中的设备最多只有15种信号和10种信号传送管理器，树型结构的层数小于等于10
输出：
针对每一个输入数据中描述的NTA(NTA1,NTA2等等)中的树结构，输出改树结构是否合法，合法的话就输出“Valid”（不输出引号），，不合法的话就输出“Invalid”（不输出引号），在各个NTA的情况之间打一个空行以分隔。
Sampal Input
4 2 3
1 2
2 1
1 0
2 2
0 2 1 0
3 2
2 2
2 3
1 2
1 2
2 1
3 2
3
a
b c
a b c b
b a b a c a * *
2
b
a b
b c * *
-1
0 0 0
Output for the Sample Input
NTA1:
Valid
Invalid