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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <vector>

#define MAX_SIZE 50000000
#define MAX_N 1005

std::vector<std::vector<short> > patterns;
short body[2][MAX_SIZE];
int prefixTable[MAX_N];


short seq[MAX_N];


int max(int a, int b){
	return a > b ? a :b;
}


int launchKmp(int seqLen, int bodyLen, int part){
	int shift = 0;
	int posInText = 0;
/*
	for(int i = 0; i < bodyLen;i++){
		printf("%d",body[part][i]);
	}
	printf("\n");*/
	while(posInText <= bodyLen - seqLen){
		//printf("shift %d  posInText %d=================\n", shift, posInText);
		while(shift < seqLen && posInText + shift < bodyLen && seq[shift] == body[part][shift + posInText]) shift++;
		if (shift == seqLen) {
			//printf("ZNALAZL \n");
			return 1;
			//shift--;//by poprawnie sie prefiks wyliczyl
		}// else printf("SHIFT %d\n",shift);
		//printf("shift %d posInText %d\n", shift,  posInText);
		posInText = posInText + shift - prefixTable[shift];
		shift = max(0,prefixTable[shift]);
		//printf("shift %d  posInText %d\n", shift, posInText);
	}
	return 0;
}

void countPrefixTable(int len){
	int pIndex = 0;
	int prefixVal = 0;
	int prefixIndex = 2;
	prefixTable[0] = -1;
	prefixTable[1] = 0;
	for(int i = 2; i <= len; i++){
		//printf("%d %d\n", i, pIndex);
		if (seq[pIndex] == seq[i]){
			pIndex++;
			prefixVal++;
		} else {
			pIndex = 0;
			prefixVal = 0;
		}
		//printf("==%d %d\n", prefixIndex, prefixVal);
		prefixIndex++;
		prefixTable[prefixIndex] = prefixVal;
	}
/*
	for(int i = 0; i < len; i++){
		printf("(%d %d) ", prefixTable[i],seq[i]);
	}
	printf("\n");*/
}

int main(){
	int n,l;
	int seqLen;
	scanf("%d %d", &n, &seqLen);
	patterns.push_back(std::vector<short>());
	for(int i = 0; i < n; i++){
		scanf("%d",&l);
		patterns.push_back(std::vector<short>(l,0));
		for(int j = 0; j < l; j++){
			scanf("%hd", &patterns.back()[j]);
		}
	}
	for(int i = 0; i < seqLen; i++){
		scanf("%hd",&seq[i]);
	}

	countPrefixTable(seqLen);
	int from = 0;
	int to = 1;
	int phaze = 1;
	int lastPointer;
	int bodyLen = 1;
	body[from][0] = 1;
	while(bodyLen < MAX_SIZE && phaze < 1000){

		if (launchKmp(seqLen,bodyLen, from)){
			printf("%d\n",phaze);
			return 0;
		}

		lastPointer = 0;
		for(int i = 0; i < bodyLen; i++){
			for(int j = 0; j < (int)patterns[body[from][i]].size(); j++ ){
				if (lastPointer >= MAX_SIZE - 2) goto search_end;
				body[to][lastPointer++] = patterns[body[from][i]][j];
			}
		}


		from = from == 0 ? 1 :0;
		to = to == 0 ? 1 : 0;
		bodyLen = lastPointer;

		phaze++;
	}
	search_end:
	printf("-1\n");
	return 0;
}