#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) {
vector<vector<int>> e(k + 1, vector<int> ());
for (int i = 0; i < m; i++)
for (auto j: b[i])
e[j].push_back(i);
vector<pair<pair<int, int>, pair<int, int>>> p(m + 1);
for (int i = 0; i <= m; i++) {
p[i].first = {-1, 0};
p[i].second = {-1, 0};
}
vector<int> v;
for (int i = n - 1; i >= 0; i--) {
int mx = 0;
for (auto j: e[c[i]]) {
int y = (j + 1) % m;
p[j].second = p[j].first;
p[j].first.first = 1; p[j].first.second = i;
if (p[y].first.second == -1 || p[y].first.second == i + 1) {
p[j].first.first = p[y].first.first + 1;
}
if (p[y].second.second == -1 || p[y].second.second == i + 1) {
p[j].first.first = max(p[j].first.first, p[y].second.first + 1);
}
p[j].first.first = min(p[j].first.first, m);
mx = max(mx, p[j].first.first);
}
if (mx == m)
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--) {
// int n, m, k;
// cin >> n >> m >> k;
// vector<int> c(n);
// for (int i = 0; i < n; i++)
// cin >> c[i];
// vector<int> a(m);
// vector<vector<int>> b(m, vector<int> ());
// for (int i = 0; i < m; i++) {
// cin >> a[i];
// for (int j = 0; j < a[i]; j++) {
// int x;
// cin >> x;
// b[i].push_back(x);
// }
// }
// cout << minimumInstructions(n, m, k, c, a, b) << '\n';
// }
// return 0;
// }
