1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cstdio>
#include <queue>
#include <vector>

int const MAX = 1001;
int n, m, a, b;
int tab[MAX+1][MAX+1];
int wzor[MAX+1];

std::queue<int> Q[2];

std::vector<int> vec;

int main(){
	int stala = 0;
	scanf("%d %d", &n, &m);
	stala += m + n;
	for(int i = 1; i <= n; ++i){
		scanf("%d", &a);
		stala += a;
		tab[i][0]=a;
		for(int j = 1; j <= a; ++j){
			scanf("%d", &b);
			tab[i][j]=b;
		}
	}
	wzor[0] = m;
	for(int j = 1; j <= m; ++j){
		scanf("%d", &b);
		wzor[j]=b;
	}
	
	int* KMP = new int[m+2];
	    KMP[0] = 0;
	    KMP[1] = 0;
	    int S = 0;
	    for(int i = 2; i <= m; i++){
	      while((S > 0) && (wzor[S+1] != wzor[i-1+1])){
		S = KMP[S];
	      }
	      if(wzor[S+1]== wzor[i-1+1]) S++;
	      KMP[i] = S;
	    }
	if(m == 1 && wzor[1] == 1){
		printf("1\n");
	}else{
		int h = 0;
		int counter = 1;
		Q[h].push(1);
		bool jest = false;
		while(counter < stala*10){
			counter++;
			//if(counter == 5) break;
			while(!Q[h].empty()){
				int x = Q[h].front();
				a = tab[x][0];
				for(int j = 1; j <= a; ++j){
					//printf("%d ", tab[x][j]);
					Q[(h+1)%2].push(tab[x][j]);
					vec.push_back(tab[x][j]);
				}
				Q[h].pop();
			}
			//printf("\n");
			////////
			long long int i = 1;
		    long long int j = 0;
		    while (i <= vec.size()-m+1){
		    	j = KMP[j];
		    	while((j < m) && (wzor[j+1]==vec[i+j-1])) {
		    	//	printf("wzor[j+1]==vec[i+j-1] %d == %d",wzor[j+1] ,vec[i+j-1]);
		    		j++;
				}
			//	printf("\n");
		    	if(j==m) {
		    		printf("%d\n",counter);
		    		jest = true;
		    		break;
				}
				i=i+((1>j-KMP[j])?1:(j-KMP[j]));
		     }
			////////
			vec.clear();
			h++;
			h %= 2;
			if(jest) break;
		}    
		if(!jest) printf("-1\n");
	}

	    
	delete [] KMP;
//	for(int i = 1; i <= n; ++i){
//		printf("%d : ", tab[i][0]);
//		for(int j = 1; j <=  tab[i][0]; ++j){
//			printf("%d ", tab[i][j]);
//		}
//		printf("\n");
//	}
}