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
program eks;//eksplozja komórkowa,runda 5-B                2.10.2015
uses Dos;
const lTmax=10000000; lSmax=1000; nmax=500; mmax=1000; hmax=500;
  lhmax=500;
type Ti=longint;  Tw=longint;
var n,m,t,lS,lT,lT1,lT2:Ti; rozw:boolean=false; //bo:boolean=true;
  T1,T2:array[0..lTmax] of Tw; //ciągi komórek porówn ze wzorcem
  S:array[0..lSmax] of Tw; //wzorzec S
  HH:array[1..hmax] of record lH:Tw; H:array[1..lhmax] of Tw end; 
  pi:array[1..mmax] of Tw;//wartosci funkcji prefiksowej wzorca

procedure Dane; var i,j:Ti;
begin
  readln(n,m); lS:=m;//n:typy komórek, m:dl sekwencji S
  for i:=1 to n do with HH[i] do
  begin read(lH);
    for j:=1 to lH do read(H[j]) //powstajace ciagi komórek
  end;  
  for i:=1 to lS do read(S[i]); //wzorzec
  if lS<20 then lT:=4000000 else lT:=lTmax;
end;//Dane

procedure CPF(m:Ti; var P:array of Tw);//Compute-Prefix-Function
var k,q:Ti;
begin pi[1]:=0; k:=0;
  for q:=2 to m do
  begin
    while (k>0) and (P[k+1] <> P[q]) do k:=pi[k];//while
    begin
      if P[k+1]=P[q] then k+=1;
      pi[q]:=k
    end
  end//q
end;//CPF

procedure KMPmatcher(n,m:Ti;var T,P:array of Tw);//P[1..m],T[1..n]
var q,i:Ti;
begin q:=0; //l pasujących symboli
  for i:=1 to n do
  begin
    while (q>0) and (P[q+1]<>T[i]) do q:=pi[q];//nast symb nie pasuje
    if P[q+1]=T[i] then q+=1;//nastepny symbol pasuje
    if q=m then //czy całe P jest dopasowane?
     begin rozw:=true; exit end //znalezione 1-e rozwiazanie
  end;//i
end;//KMPmatcher

procedure genT(l1:Ti; var l2:Ti; var T1,T2: array of Tw);
        //generator T2 na podst T1
var i,k:Tw;
begin  l2:=0;//licznik elementów ciągu wynikowego
  for i:=1 to l1 do  with HH[T1[i]] do
  for k:=1 to lH do
  begin l2+=1;
    if l2>lT then begin t:=-1; rozw:=true; exit; end;
    T2[l2]:=H[k]
  end;//k,i
end;//genT

begin  Dane;
  if (lS=1) and (S[1]=1) then begin writeln(1); exit; end;
  CPF(lS,S); //obl pi[i]
  lT1:=1; T1[1]:=1; t:=1;
  repeat  t+=1;
    if not Odd(t) then 
    begin genT(lT1,lT2,T1,T2);if t>0 then KMPmatcher(lT2,lS,T2,S) end
     else begin genT(lT2,lT1,T2,T1);if t>0 then KMPmatcher(lT1,lS,T1,S) end
  until rozw;
  writeln(t)
end.