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
123
124
125
126
127
128
// 1. 10 generacji ręcznie (dla symboli od 1 do 500):
// a) czy jest match w środku
// b) jakie prefixy patternu pasują na koniec (max prefix)
// c) sakie suffixy patternu pasują na początek (max suffix)
// 2. Kiedy osiągany jest dany symbol po raz pierwszy?
// 3. Kiedy osiągana jest dana para po raz pierwszy?
// 4. Które kombinacje prefix-suffix (1b, 1c) dają match?
//
// No i teraz:
// - 2+1a (500 x 11)
// - 4+3 (500 x 500 x 11)
//
// Czasy generowania:
// 1a) 1001 x 11 x (500 + 1000)
// 1b) czytamy z tabelek z 1a
// 1c) czytamy z tabelek z 1a
// 2+3. BFS (500x500 + 1000)
// 4. 1000x1000

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

queue<pair<int, int> > q;
vector<vector<int> > time;

void Enqueue(const int l, const int r, const int t) {
  if (time[l][r] >= 0) return;
  time[l][r] = t;
  q.push(make_pair(l, r));
}

// http://stackoverflow.com/questions/13792118/kmp-prefix-table
template <typename Iterator>
vector<int> PrefixFunction(const Iterator begin, const Iterator end) {
  const int size = end - begin;
  vector<int> p(size);
  int j = 0;
  for (int i = 1; i < size; ++i) {
    while (j > 0 && *(begin + j) != *(begin + i)) j = p[j - 1];
    if (*(begin + j) == *(begin + i)) ++j;
    p[i] = j;
  }
  return p;
}

int main() {
  int n;
  int m;
  scanf("%d%d", &n, &m);
  vector<vector<int> > h(n);
  for (int i = 0; i < n; ++i) {
    int l;
    scanf("%d", &l);
    h[i].resize(l);
    for (int j = 0; j < l; ++j) {
      scanf("%d", &h[i][j]);
      --h[i][j];
    }
  }
  vector<int> s(m);
  for (int i = 0; i < m; ++i) {
    scanf("%d", &s[i]);
    --s[i];
  }

  vector<vector<vector<int> > > transition(11, vector<vector<int> >(n, vector<int>(m + 1, 0)));
  // Identycznosc.
  for (int i = 0; i <= 10; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k <= m; ++k) transition[i][j][k] = k;
  // Nic nie pasuje...
  for (int j = 0; j < n; ++j) for (int k = 0; k < m; ++k) transition[0][j][k] = 0;
  // ...z wyjątkiem symboli wzorca.
  for (int k = 0; k < m; ++k) transition[0][s[k]][k] = k + 1;

  // Wypelnienie dynamiczne reszty, co konczy krok 1a.
  for (int i = 0; i < 10; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k <= m; ++k) for (int l = 0; l < h[j].size(); ++l) transition[i + 1][j][k] = transition[i][h[j][l]][transition[i + 1][j][k]];

  // 1b+c.
  vector<vector<int> > best_prefix(11, vector<int>(n, 0));
  vector<vector<int> > best_suffix(11, vector<int>(n + 1, m));
  for (int i = 0; i <= 10; ++i) for (int j = 0; j < n; ++j) {
    best_prefix[i][j] = transition[i][j][0];
    for (int k = m; k >= 0; --k) if (transition[i][j][k] == m) best_suffix[i][j] = k;
  }

  // 2+3.
  time.resize(n, vector<int>(n + 1, -1));
  Enqueue(0, n, 0);
  while (!q.empty()) {
    const pair<int, int> p = q.front();
    const int l = p.first;
    const int r = p.second;
    const int t = time[l][r];
    q.pop();
    if (r == n) {
      for (int i = 0; i < h[l].size(); ++i) {
        Enqueue(h[l][i], n, t + 1);
        if (i) Enqueue(h[l][i - 1], h[l][i], t + 1);
      }
    } else {
      Enqueue(h[l].back(), h[r][0], t + 1);
    }
  }

  // 4.
  vector<vector<bool> > fit(m + 1, vector<bool>(m + 1, false));
  for (int i = 0; i <= m; ++i) fit[i][i] = true;
  {
    const vector<int> p = PrefixFunction(s.begin(), s.end());
    for (int i = 1; i <= m; ++i) for (int j = 0; j <= m; ++j) if (fit[p[i - 1]][j]) fit[i][j] = true;
  }
  {
    const vector<int> p = PrefixFunction(s.rbegin(), s.rend());
    for (int i = 0; i <= m; ++i) for (int j = m - 1; j >= 0; --j) if (fit[i][m - p[m - j - 1]]) fit[i][j] = true;
  }

  // Wynik.
  int ret = -1;
  for (int i = 0; i < n; ++i) for (int j = 0; j <= n; ++j) if (time[i][j] != -1) for (int k = 0; k <= 10; ++k) if (fit[best_prefix[k][i]][best_suffix[k][j]]) {
    if (ret == -1 || time[i][j] + k < ret) ret = time[i][j] + k;
    break;
  }
  printf("%d\n", ret + 1);

  return 0;
}