1 #include <cstdio>  2 #include <cstdlib>  3 #include <string>  4 #include <iostream>  5 #include <cstring>  6 #include <algorithm>  7 #include <sstream>  8 #include <cctype>  9 #include <vector> 10 #include <map> 11 #include <set> 12 #include <iterator> 13 #include <functional> 14 #include <cmath> 15 #include <numeric> 16 #include <ctime> 17 using namespace std; 18 typedef long long LL; 19 typedef pair<int,int> PII; 20 typedef vector<int> VI; 21 #define PB push_back 22 #define MP make_pair 23 #define SZ size() 24 #define CL clear() 25 #define AA first 26 #define BB second 27 #define EPS 1e-8 28 #define ZERO(x) memset((x),0,sizeof(x)) 29 const int INF = ~0U>>1; 30 const double PI = acos(-1.0); 31  32 int n,m,k; 33 char in[1000]; 34 vector<PII> v[1000][1000]; 35 int tree[10000]; 36 char ch[2]; 37  38 bool isAccepted(int sig){ 39     return sig>=n-m; 40 } 41  42 bool dfs(int rt,int sig){ 43 //    printf("rt = %d sig = %d\n",rt,sig); 44  45     int rtVal = tree[rt]; 46  47     if( rtVal==-1 ){ 48         return isAccepted(sig); 49     } 50 //    printf("rtVal = %d\n",rtVal); 51     bool res = false; 52     for(int i=0;i<v[sig][rtVal].SZ;i++){ 53         res = dfs(rt<<1,v[sig][rtVal][i].AA); 54         if(!res) continue; 55         res &= dfs(rt<<1|1,v[sig][rtVal][i].BB); 56         if( res ) break; 57     } 58  59     return res; 60 } 61  62 int main(){ 63     int kase = 1; 64     while( scanf("%d%d%d",&n,&m,&k)!=EOF ){ 65         getchar(); 66         for(int i=0;i<1000;i++) for(int j=0;j<1000;j++) v[i][j].CL; 67         if( n==0&&m==0&&k==0 ) break; 68         for(int i=0;i<n;i++){ 69             for(int j=0;j<k;j++){ 70                 gets(in); 71                 istringstream sss(in); 72                 int a,b; 73                 while( sss>> a >> b ){ 74                     v[i][j].PB(MP(a,b)); 75 //                    printf("v[%d][%d].PB(%d,%d)\n",i,j,a,b); 76                 } 77             } 78         } 79 //        puts("*****"); 80         if( kase!=1 ) puts(""); 81         printf("NTA%d:\n",kase++); 82         int q; 83         while( true ){ 84             memset(tree,-1,sizeof(tree)); 85             scanf("%d",&q); 86             if( q==-1 ) break; 87             for(int i=1;i<=(1<<(q+1))-1;i++){ 88                 scanf("%s",&ch); 89                 if( strcmp(ch,"*")==0 ){ 90                     tree[i] = -1; 91                 } else { 92                     tree[i] = ch[0]-‘a‘; 93                 } 94 //                printf("%d ",tree[i]); 95             }//puts(""); 96  97             bool ok = dfs(1,0); 98             if(ok) puts("Valid"); 99             else puts("Invalid");100         }101 102     }103     return 0;104 }