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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// typedef pair<int, int> pii;
const int N_MAX = 500+10; const int M_MAX = 1000+10; const int TRIES = 5;

int n, m; int l[N_MAX]; vector<int> h[N_MAX]; int S[M_MAX];

int first[N_MAX]; int kmp_T[M_MAX];

void calc_kmp_T() {
  for (int i = 0; i <= m; i++) kmp_T[i] = -1;
  for (int i = 1; i <= m; i++) {
    int pos = kmp_T[i-1];
    while((pos != -1) && (S[pos] != S[i-1])) pos = kmp_T[pos];
    kmp_T[i] = pos+1;
  }
}

void calc_first() {
  for (int i = 1; i <= n; i++) first[i] = -1;
  first[1] = 1;

  queue<int> q; q.push(1);
  while (!q.empty()) {
    auto s = q.front(); q.pop();
    for (auto z : h[s]) {
      if (first[z] == -1) {
        first[z] = first[s] + 1;
        q.push(z); 
      }
    }
  }

  // cerr << "first[";
  // for (int i = 1; i <= n; i++) cerr << first[i] << ' ';
  // cerr << "]\n";
}

void build_next(vector<int>& W) {
  vector<int> nW;
  for (auto x : W) { for (auto y : h[x]) nW.push_back(y); }
  swap(W, nW);
}

bool search_kmp(vector<int>& W) {
  int sp = 0, kp = 0;
  while (sp < W.size()) {
    while ((kp != -1) && (kp == m || S[kp] != W[sp])) kp = kmp_T[kp];
    kp++; sp++;
    if (kp == m) return true;
  }
  return false;
}

int build_search(int k) {
  if (first[k] == -1) return -1;
  // cerr << "build_search " << k << '\n';
  vector<int> W; W.push_back(k);

  int d = first[k];
  // cerr << "d: " << d << '\n';
  while (W.size() < m) {
    build_next(W); d++;
  }
  // cerr << "d: " << d << '\n';

  for (int t = 0; t < TRIES; t++) {
    // cerr << "d=" << d << '\n';
    // cerr << "W=[";
    // for (auto x : W) cerr << x << " ";
    // cerr << "]\n";
    if (search_kmp(W)) return d;
    build_next(W); d++;
  }
  // cerr << "d: " << d << '\n';
  return -1;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", l+i);
    for (int j = 0; j < l[i]; j++) { int hij; scanf("%d", &hij); h[i].push_back(hij); }
  }
  for (int i = 0; i < m; i++) { scanf("%d", S+i); }

  calc_kmp_T();
  calc_first();

  int ans = -1;
  for (int i = 1; i <= n; i++) {
    // cerr << "cell: " << i << '\n';
    int res = build_search(i);
    // cerr << "res: " << res << '\n';
    if (ans == -1) ans = res;
    else ans = (res == -1) ? ans : min(ans, res);
  }

  printf("%d\n", ans);
  return 0;
}