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
#include <string>
#include <vector>
#include <stdio.h>

using namespace std;
// po kompilacji parametry należy przekazać poprzez argumenty wywołania programu (1. ciąg do przeszukania 2. ciąg do znalezienia)


vector<int> przemiany[501];
vector<int> S;
vector<int> k1;
vector<int> k2;
std::vector<int>::iterator it;

bool check (vector<int> wzorzec, vector<int> napis) {
   unsigned int m, i, k;
   vector<int> T; // tablica częściowego dopasowania
   vector<int> places;
   //cout << "Wzorzec: " << wzorzec.length() << endl;
   //cout << "Napis: " << napis << endl;
   //for(i=0 ; napis[i]!='\0' ; i++)
     //cout << "napis[" << i << "] = " << napis[i] << endl;
   for(i=0 ; i<napis.size() ; i++) {
     //printf("B %d\n", i);
     //printf("B %d\n", napis[i]);
     //printf("B %d\n", wzorzec[0]);
     if( napis[i] == wzorzec[0] )
       T.push_back(i);
   }
   //for(i=0 ; i<T.size() ; i++)
     //printf("A %d\n", i);
     //cout << "T[" << i << "] = " << T[i]<< endl;
   
   if (T.size()==0)
     return false;
   //printf("F\n");
   
   for( i=0, k=0, m=T[k] ; (m+i) <= napis.size() && k < T.size(); i++ ) {
     //printf("C %d\n", i);
     if( wzorzec[i] != napis[m+i] ) {  // nie pasuje
       m=T[++k];
       i=0;
     }
     if( i == wzorzec.size()-1 ) {   // pasuje
       places.push_back(T[k]);
       m=T[++k];
       i=0;
     }
     //printf("C %d\n", i);
   }
   
   //printf("G \n");
   //for(i=0 ; i < places.size() ; i++)
   //  cout << "Places[" << i << "] = " << places[i]<< endl; // wypisz miejsca występowania żądanego ciągu
   if (places.size()>0)
    return true;
   else
     return false;
   }


int main()
{
  int n,m,l,h;
  scanf("%d %d", &n, &m);
  for (int i=1; i<=n; ++i) {
    scanf("%d", &l);
    for (int j=0; j<l; ++j) {
      scanf("%d", &h);
      przemiany[i].push_back(h);
    }
  }
  
  for (int i=0; i<m; ++i) {
    scanf("%d", &h);
    S.push_back(h);
  }
  
  
  k1.push_back(1);
  bool result;
  
  int sum=0;
  
  for (int i=1; i<1000000; ++i) {
    //printf("i= %d \n", i);
    //jezeli jest to zwroc wynik
    
    sum+=k1.size();
    if (sum>30000000) break;
    //printf("sum=%d\n", sum);
    
    result = check(S,k1);
    if (result) {
      printf("%d\n", i);
      break;
    }
    
    for (it=k1.begin(); it<k1.end(); it++) {
      k2.insert (k2.end(), przemiany[*it].begin(),przemiany[*it].end());
    }
    
    swap(k1,k2);
    k2.clear();
    
  }
  if (!result)
    printf("-1\n");
  
  
}