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
#include <cstdio>
#include <vector>
using namespace std;

#define MAX_N 500
#define MAX_M 1000

int n,m;
vector<int> H[MAX_N];
int S[MAX_M+1];
vector<int> P;

int main(){
    scanf("%d%d",&n,&m);
    for(int a=0;a<n;++a){
        int l;
        scanf("%d",&l);
        H[a].reserve(l);
        for(int b=0;b<l;++b){
            int q;
            scanf("%d",&q);
            --q;
            H[a].push_back(q);
        }
    }
    for(int a=0;a<m;++a){
        scanf("%d",S+a);
        --S[a];
    }
    S[m]=-1;

    P.push_back(0);
    int i=1;
    int t=0;
    while(i<=m){
        while(t>0 && S[t]!=S[i])t=P[t-1];
        if(S[t]==S[i])++t;
        P.push_back(t);
        ++i;
    }

    vector<int>* V1=new vector<int>;
    vector<int>* V2=new vector<int>;
    V1->push_back(0);

    int ans=1;
    while(1){
        P.resize(m+1);
        i=m+1;
        t=P.back();
        while(i<=m+V1->size()){
            while(t>0 && S[t]!=V1->at(i-m-1))t=P[t-1];
            if(S[t]==V1->at(i-m-1))++t;
            P.push_back(t);
            if(t==m){
                printf("%d",ans);
                return 0;
            }
            ++i;
        }

        V2->clear();
        for(int x:(*V1)){
            for(int y:H[x]){
                V2->push_back(y);
            }
        }
        swap(V1,V2);

        ++ans;
    }

    return 0;
}