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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>

using namespace std;

int* pi = nullptr;

int *compute_prefix_function(int *pattern, int psize)
{
	int k = -1;
	int i = 1;
	int *pi = (int*) malloc(sizeof(int)*psize);
	if (!pi)
		return NULL;

	pi[0] = k;
	for (i = 1; i < psize; i++) {
		while (k > -1 && pattern[k+1] != pattern[i])
			k = pi[k];
		if (pattern[i] == pattern[k+1])
			k++;
		pi[i] = k;
	}
	return pi;
}

int kmp(int *target, int tsize, int *pattern, int psize)
{
	int i;
	int k = -1;
	if (!pi)
		return -1;
	for (i = 0; i < tsize; i++) {
		while (k > -1 && pattern[k+1] != target[i])
			k = pi[k];
		if (target[i] == pattern[k+1])
			k++;
		if (k == psize - 1) {
			return i-k;
		}
	}
	return -1;
}

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

	vector< vector< int > > c( n );
	for ( int i = 0; i < n; ++i )
	{
		int k;
		cin >> k;
		c[ i ].resize( k );
		for ( int j = 0; j < k; ++j )
		{
			cin >> c[ i ][ j ];
			--c[ i ][ j ];
		}
	}

	vector< int > p( m );
	for ( int i = 0; i < m; ++i )
	{
		cin >> p[ i ];
		--p[ i ];
	}
	pi = compute_prefix_function( &p[ 0 ], p.size() );

	const int LIMIT = 10000000;
	vector< int > t( LIMIT );
	int ops = 0;
	t[ 0 ] = 0;
	int tSize = 1;
	int step = 1;
	while ( 1 )
	{
		const int foundPos = kmp( &t[ 0 ], tSize, &p[ 0 ], p.size() );
		if ( foundPos != -1 )
		{
			cout << step;
			return 0;
		}

		int newSize = 0;
		for ( int i = 0; i < tSize; ++i )
		{
			newSize += c[ t[ i ] ].size();
		}
		ops += newSize;
		if ( newSize > LIMIT || ops > LIMIT )
		{
			cout << -1;
			return 0;
		}
		int pos = newSize - 1;
		for ( int i = tSize - 1; i >= 0; --i )
		{
			const int p = t[ i ];
			const vector< int >& a = c[ p ];
			for ( int j = a.size() - 1; j >= 0; --j, --pos )
			{
				t[ pos ] = a[ j ];
			}
		}
		tSize = newSize;

		++step;
	}

	return 0;
}