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
#include <iostream>
#include <vector>

using namespace std;

vector<int> P(1001);
int m; // size of P
vector<int> b(1001);

void kmpPreprocess() {
  int i = 0, j = -1; b[0] = -1;
  while (i < m) {
    while (j >= 0 && P[i] != P[j]) j = b[j];
    i++; j++;
    b[i] = j;
} }

bool kmpSearchShort(vector<int> T, int sz) { // this is similar as kmpPreprocess(), but on string T
  int i = 0, j = 0; // starting values
  while (i < sz) { // search through string T
    while (j >= 0 && T[i] != P[j]) {
	j = b[j]; // if different, reset j using b
    }
    i++; j++; // if same, advance both pointers
    if (j == m) { // a match found when j == m
//      cout << "match at " << i - j << " where sz " << sz << " and m " << m << endl;
//      for (int q = i - j; q < i; ++q) {
//	cout << "T[q] " << T[q] << " P[q] " << P[q] << endl;
//      }
      return true;
      // j = b[j]; // prepare j for the next possible match
    } 
  } 
  return false;
}

#define MAXIT 20000
#define MAXLEN 500000000

int main() {
	int n;
	cin >> n;
	cin >> m;

	vector<vector<int> > pats(n+1);

	for (int i = 0; i < n; ++i) {
		int patsize;
		int x;
		cin >> patsize;
		for (int j = 0; j < patsize; ++j) {
			cin >> x;
			pats[i+1].push_back(x);
		}
	}

	for (int i = 0; i < m; ++i) {
		int x;
		cin >> x;
		P[i] = x;
	}

	vector<int> kom[2];

	kom[0].push_back(1);

	kmpPreprocess();

	for (int y = 1; y < MAXIT; ++y) {
		int nu = y % 2;
		int ol = 1 - nu;
//		cout << "kom generation " << y << "| ";
//		for (int z = 0; z < kom[ol].size(); ++z) {
//			cout << kom[ol][z] << " | ";
//		}
//		cout << endl;
		
		kom[nu].clear();
		int cnt = kom[ol].size();
		if (cnt > MAXLEN) {
//			cout << "maxlen!" << endl;
			cout << "-1" << endl;
			return 0;
		}
		for (int i = 0; i < kom[ol].size(); ++i) {
			cnt += kom[ol].size();
			if (cnt > MAXLEN) {
//				cout << "maxlen!!" << endl;
				cout << "-1" << endl;
				return 0;
			}
			int sel = kom[ol][i];
			for (int j = 0; j < pats[sel].size(); ++j) {
				kom[nu].push_back(pats[sel][j]);
			}
		}

		if ((kom[nu].size() >= m) && (kmpSearchShort(kom[nu], kom[nu].size()) == true)) {
			cout << y + 1 << endl;
			return 0;
		}

	}

	cout << "-1" << endl;

	return 0;
}