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
#include <iostream>
#include <vector>
//#include <cstdlib>
//#include <conio.h>

using namespace std;

vector<int> teraz, nowy;
vector<int> *a;
int *wzor;
int n, m, d;
int * pref;

bool ok(){
    if(teraz.size()<m) return 0;
    else{
        int t=0;
        int w=teraz.size();
        for (int i = 0; i < w; i++) {
            while (t > 0 && teraz[i] != wzor[t] ) t=pref[t-1];
            if(teraz[i] == wzor[t]) t++;
            if(t==m) return true;
        }
    }
    return false;
}

void wyznacz_p(){
    pref[0] = 0;
	int t = pref[0];
	for (int i = 1; i < m; i++) {
	     while (t > 0 && wzor[i] != wzor[t] ) t=pref[t-1];
         if(wzor[i] == wzor[t]) t++;
         pref[i] = t;
         //cout << pref[i];
	}
}

void ewoluuj(){
    vector<int>::iterator it, it2;
    nowy.clear();
    for(it=teraz.begin(); it!= teraz.end(); it++){
        for(it2=a[*it].begin(); it2!=a[*it].

        end(); it2++){
            nowy.push_back(*it2);
        }
    }
    teraz=nowy;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    a=new vector<int>[n];
    wzor = new int[m];
    int pom;
    int max=0;
    for(int i =0; i<n; ++i){
        cin >> pom;
        if(pom>max)max=pom;
        a[i].resize(pom);
        for(int j=0; j<pom; j++){
            cin >> d;
            a[i][j]=(d-1);
        }
    }
    for(int i=0; i<m; ++i){
        cin >> wzor[i];
        --wzor[i];
    }
    pref=new int[m];
    int j=0;
    int s=1;
    wyznacz_p();
    teraz.push_back(0);
    while(j<4000000){
        //cout << endl;
       // for(vector<int>::iterator it = teraz.begin(); it!=teraz.end(); it++) cout << *it << " ";
       // cout << endl << endl;
        if(ok()){
            cout <<  s;
            return 0;
        }
        else ewoluuj();
        s++;
        j+=(m+teraz.size());
        if(teraz.size()*max+j>50000000) break;

     //   getch();
    }
    cout << -1;

    return 0;
}