#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
// const int N = 1000 + 10;
// const int md = 1e9 + 7;
// const int INF = 5e6;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
if (n <= 20000 && m <= 2000 && !n) {
vector<vector<bool>> ok(n + 1, vector<bool> (m + 1));
for (int i = 0; i < m; i++) {
vector<bool> qw(k + 1);
for (int j = 0; j < a[i]; j++)
qw[b[i][j]] = 1;
for (int j = 0; j < n; j++) {
if (qw[c[j]] == 1)
ok[j][i] = 1;
}
}
vector<vector<int>> dp(n + 2, vector<int> (m + 2));
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (ok[i][j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
}
}
}
vector<int> v;
for (int i = 0; i <= (n - m); i++) {
for (int j = 0; j < m; j++) {
if (j == 0) {
if (dp[i][j] == m)
v.push_back(i);
} else {
if (dp[i][j] == (m - j) && dp[i + (m - j)][0] >= j)
v.push_back(i);
}
}
}
int ans = 0;
int el = n - 1;
while (el != -1) {
int l = lower_bound(v.begin(), v.end(), (el - m + 1)) - v.begin();
if (l == (int) v.size() || v[l] > el) {
ans = -1;
break;
} else {
ans++;
el = v[l] - 1;
}
}
return ans;
} else {
vector<vector<int>> elems(k + 1, vector<int> ());
for (int i = 0; i < n; i++)
elems[c[i]].push_back(i);
vector<int> cl(k + 1);
for (int i = 0; i < m; i++) {
for (auto j: b[i])
cl[j] = i;
}
vector<int> dp(n + 1);
vector<int> v;
for (int j = m - 1; j >= 0; j--) {
if (j == m - 1) {
for (auto qo: b[j])
for (auto i: elems[qo]) {
dp[i] = 1;
}
} else {
for (auto qo: b[j])
for (auto i: elems[qo]) {
if ((i + 1) < n && cl[c[i + 1]] == j + 1) {
dp[i] = dp[i + 1] + 1;
}
}
}
}
for (int j = m - 1; j >= 0; j--) {
if (j == m - 1) {
for (auto qo: b[j])
for (auto i: elems[qo]) {
if (j == 0) {
if (dp[i] == m) {
v.push_back(i);
}
} else {
if (dp[i] == 1 && i + 1 < n && cl[c[i + 1]] == 0 && dp[i + 1] >= (m - 1))
v.push_back(i);
}
}
} else {
for (auto qo: b[j])
for (auto i: elems[qo]) {
if ((i + 1) < n && cl[c[i + 1]] == j + 1) {
if (j == 0) {
if (dp[i] == m)
v.push_back(i);
} else {
if (dp[i] == (m - j) && i + (m - j) < n && cl[c[i + (m - j)]] == 0 && dp[i + (m - j)] >= j)
v.push_back(i);
}
}
}
}
}
sort(v.begin(), v.end());
int ans = 0;
int el = n - 1;
while (el != -1) {
int l = lower_bound(v.begin(), v.end(), (el - m + 1)) - v.begin();
if (l == (int) v.size() || v[l] > el) {
ans = -1;
break;
} else {
ans++;
el = v[l] - 1;
}
}
return ans;
}
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// vector<int> c = {0, 1};
// vector<vector<int>> b = {{0, 1}};
// vector<int> a = {2};
// cout << minimumInstructions(2, 1, 2, c, a, b) << '\n';
// }
// return 0;
// }
