#include <iostream> #include <vector> using namespace std; typedef long long ll; const ll P = 90000007; ll n, m; ll Hasz(vector<ll>& H, vector<ll>& p, ll po, ll ko) { return H[po] - p[ko - po + 1] * H[ko + 1]; } bool Spr(vector<ll>& c, ll wzo) { ll dl = c.size(); if (dl < m) return false; vector<ll> p(dl); p[0] = 1; for (int i = 1; i < dl; ++i) p[i] = p[i - 1] * P; vector<ll> H(dl + 1); H[dl] = 0; for (int i = dl - 1; i >= 0; --i) H[i] = H[i + 1] * P + c[i]; for (int i = 0; i <= dl - m; ++i) if (Hasz(H, p, i, i + m - 1) == wzo) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin >> n >> m; vector< vector<int> > K(n); int a, b; for (int i = 0; i < n; ++i) { cin >> a; for (int j = 0; j < a; ++j) { cin >> b; K[i].push_back(b); } } vector<ll> wzo(m); for (int i = 0; i < m; ++i) cin >> wzo[i]; vector<ll> p(m); p[0] = 1; for (int i = 1; i < m; ++i) p[i] = p[i - 1] * P; vector<ll> H(m + 1); H[m] = 0; for (int i = m - 1; i >= 0; --i) H[i] = H[i + 1] * P + wzo[i]; ll Hw = Hasz(H, p, 0, m - 1); vector<ll> c1, c2; c1.push_back(1); if (m == 1 && wzo[0] == 1) { cout << "1"; return 0; } int nr = 2; while (1) { if (nr % 2 == 0) { c2.clear(); for (int i = 0; i < c1.size(); ++i) { for (int j = 0; j < K[c1[i] - 1].size(); ++j) c2.push_back(K[c1[i] - 1][j]); if (Spr(c2, Hw)) { cout << nr; return 0; } if (c2.size() > 10000 || nr == 1000) { cout << "-1"; return 0; } } } else { c1.clear(); for (int i = 0; i < c2.size(); ++i) { for (int j = 0; j < K[c2[i] - 1].size(); ++j) c1.push_back(K[c2[i] - 1][j]); if (Spr(c1, Hw)) { cout << nr; return 0; } if (c1.size() > 10000 || nr == 1000) { cout << "-1"; return 0; } } } ++nr; } return 0; }
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 | #include <iostream> #include <vector> using namespace std; typedef long long ll; const ll P = 90000007; ll n, m; ll Hasz(vector<ll>& H, vector<ll>& p, ll po, ll ko) { return H[po] - p[ko - po + 1] * H[ko + 1]; } bool Spr(vector<ll>& c, ll wzo) { ll dl = c.size(); if (dl < m) return false; vector<ll> p(dl); p[0] = 1; for (int i = 1; i < dl; ++i) p[i] = p[i - 1] * P; vector<ll> H(dl + 1); H[dl] = 0; for (int i = dl - 1; i >= 0; --i) H[i] = H[i + 1] * P + c[i]; for (int i = 0; i <= dl - m; ++i) if (Hasz(H, p, i, i + m - 1) == wzo) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin >> n >> m; vector< vector<int> > K(n); int a, b; for (int i = 0; i < n; ++i) { cin >> a; for (int j = 0; j < a; ++j) { cin >> b; K[i].push_back(b); } } vector<ll> wzo(m); for (int i = 0; i < m; ++i) cin >> wzo[i]; vector<ll> p(m); p[0] = 1; for (int i = 1; i < m; ++i) p[i] = p[i - 1] * P; vector<ll> H(m + 1); H[m] = 0; for (int i = m - 1; i >= 0; --i) H[i] = H[i + 1] * P + wzo[i]; ll Hw = Hasz(H, p, 0, m - 1); vector<ll> c1, c2; c1.push_back(1); if (m == 1 && wzo[0] == 1) { cout << "1"; return 0; } int nr = 2; while (1) { if (nr % 2 == 0) { c2.clear(); for (int i = 0; i < c1.size(); ++i) { for (int j = 0; j < K[c1[i] - 1].size(); ++j) c2.push_back(K[c1[i] - 1][j]); if (Spr(c2, Hw)) { cout << nr; return 0; } if (c2.size() > 10000 || nr == 1000) { cout << "-1"; return 0; } } } else { c1.clear(); for (int i = 0; i < c2.size(); ++i) { for (int j = 0; j < K[c2[i] - 1].size(); ++j) c1.push_back(K[c2[i] - 1][j]); if (Spr(c1, Hw)) { cout << nr; return 0; } if (c1.size() > 10000 || nr == 1000) { cout << "-1"; return 0; } } } ++nr; } return 0; } |