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
117
118
119
120
121
122
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_N = 500;
const int MAX_M = 1000;
const int MAX_CELLS = 15000000;

short cells[2][MAX_CELLS + 1];
vector<short> rep[MAX_N + 1];
short seq[MAX_M + 1];
bool can_rep[MAX_N + 1];
int pi[MAX_M + 1];

void compute_pi(int m) {
    pi[1] = 0;
    int k = 0;
    for (int q = 2; q <=m; q++) {
        while ((k > 0) && (seq[k + 1] != seq[q])) {
            k = pi[k];
        }
        if (seq[k + 1] == seq[q]) {
            k++;
        }
        pi[q] = k;
    }
}

bool find(int to_cells, int to_cells_size, int m) {
    int q = 0;
    for (int i = 1; i <= to_cells_size; i++) {
        while ((q > 0) && (seq[q + 1] != cells[to_cells][i])) {
            q = pi[q];
        }
        if (seq[q + 1] == cells[to_cells][i]) {
            q++;
        }
        if (q == m) {
            return true;
        }
    }
    return false;
}

int simulate(int n, int m) {
    int from_cells = 0;
    int from_cells_size = 1;
    cells[0][1] = 1;
    int to_cells = 1;
    int to_cells_size = 0;
    int minute = 1;
    while (true) {
        minute++;
        // printf("----------minute: %d----------\n", minute);
        to_cells_size = 0;
        for (int i = 1; i <= from_cells_size; i++) {
            short from_cell = cells[from_cells][i];
            // printf("%hd -> ", from_cell);
            for (int j = 0; j < rep[from_cell].size(); j++) {
                short to_cell = rep[from_cell][j];
                // printf("%hd ", to_cell);
                cells[to_cells][++to_cells_size] = to_cell;
                if (to_cells_size > MAX_CELLS) {
                    if (find(to_cells, to_cells_size, m)) {
                        return minute;
                    }
                    return -1;
                }
            }
            // printf("\n");
        }
        /*
        for (int i = 1; i <= to_cells_size; i++) {
            printf("%d ", cells[to_cells][i]);
        }
        printf("\n");
        */
        if (find(to_cells, to_cells_size, m)) {
            return minute;
        }
        int tmp = from_cells;
        from_cells = to_cells;
        to_cells = tmp;
        from_cells_size = to_cells_size;
    }
    return -1;
}

int main() {
    int n, m, l;
    short h;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        can_rep[i] = false;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &l);
        for (int j = 0; j < l; j++) {
            scanf("%hd", &h);
            rep[i].push_back(h);
            can_rep[i] = true;
        }
    }
    for (int i = 1; i <= m; i++) {
        scanf("%hd", &seq[i]);
    }

    int res = 0;
    for (int i = 1; i <= m; i++) {
        if (!can_rep[seq[i]]) {
            res = -1;
        }
    }
    if (res != -1) {
        compute_pi(m);
        res = simulate(n, m);
    }
    printf("%d\n", res);

    return 0;
}