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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOR(a,b,e) for(int a=b;a<=(e);++a)

int n, m;
const int MAX_N = 501;
const int MAX_M = 1001;

vector<int> H[MAX_N];
int S[MAX_M];

class CHash {
    const long long BASE = 1000000007;
    const long long p = 2011;
    vector<long long> pp;
public:
    CHash(int n_max) {
        pp.resize(n_max + 1);
        pp[0] = 1;
        REP(x, n_max)
            pp[x + 1] = pp[x] * p % BASE;
    }
    void create(int* in, long long* out, int n) {
        out[0] = 0;
        REP(x, n)
            out[x + 1] = ((out[x] * p) + in[x]) % BASE;
    }
    long long slice(long long* in, int begin, int end) {
        long long ret = (in[end] - in[begin]*pp[end-begin]) % BASE;
        return ret < 0 ? ret + BASE : ret;
    }
    long long equals(long long h1, long long h2) {
        return (h1 - h2) % BASE == 0;
    }
};

const int MAX_HASH = 15000001;

long long h[MAX_HASH];
int evolve[2][MAX_HASH];
long long hashS;

#define RETURN(n) {cout<<n<<endl;return 0;}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    CHash hash(MAX_N);
    int l;
    FOR(x, 1, n) {
        cin >> l;
        vector<int>& Hx = H[x];
        Hx.resize(l);
        REP(y, l)
            cin >> Hx[y];
    }
    REP(x, m)
        cin >> S[x];
//		cerr << "Szukany ciag: "<<endl;
//		REP(x,m)
//			cerr<<S[x]<<" ";
//		cerr << endl;
    hash.create(S, h, m);
    hashS = hash.slice(h, 0, m);
    evolve[0][0] = 1;
    int len = 1, newLen;
    REP(x, n) {
//    		cerr << "Krok " << x+1 << endl;
//    		REP(y,len)
//    			cerr << evolve[x&1][y] << " ";
//				cerr << endl;
        hash.create(evolve[x & 1], h, len);
        REP(y, len - m) {
            long long subhash = hash.slice(h, y, y + m);
            if (hash.equals(subhash, hashS))
                RETURN(x + 1);
        }
        newLen = 0;
        REP(y, len) {
            vector<int>& Hx = H[evolve[x & 1][y]];
        		if(newLen+Hx.size() >= MAX_HASH) {
//							cerr<<"Krok "<<x+1<<" - nie znaleziono" << endl;
        			RETURN(-1);
        		}
            memcpy(&evolve[(~x) & 1][newLen], &Hx[0], (Hx.size() << 2));
            newLen += Hx.size();
        }
        len = newLen;
    }
    RETURN(-1);
    return 0;
}