#include "paint.h"
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define pb push_back
#define f first
#define s second
#define ll long long
const int maxn = 1e5 + 200, maxm = 1e3 + 200, inf = 1e9;
int n, m, k;
int dp[maxn], is[maxn], lst[maxn], prv[maxn], cur[maxn], mx[maxn], t[maxn * 4];
vector<int> g[maxn];
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
n = N, m = M, k = K;
for (int j = 0; j < m; ++j){
prv[j] = -inf;
cur[j] = -inf;
}
for (int i = 0; i < m; ++i){
for (auto it : B[i]){
g[it].pb(i);
}
}
for (int i = n - 1; i >= 0; --i){
mx[i] = -inf;
for (auto x : g[C[i]]){
int nx = (x + 1) % m;
if (i + 1 < n && prv[nx] != -inf){
cur[x] = min(m, prv[nx] + 1);
}
cur[x] = max(cur[x], 1);
mx[i] = max(mx[i], cur[x]);
}
if (i + 1 < n){
for (auto x : g[C[i + 1]]){
prv[x] = -inf;
}
}
for (auto x : g[C[i]]){
prv[x] = cur[x];
cur[x] = -1;
}
}
// for (int i = 0;
if (mx[0] >= m){
int ans = 1;
int pos = m - 1;
int uk = 1;
while (pos != n - 1){
int go = -1;
while (uk <= pos + 1){
if (mx[uk] >= m){
go = uk + mx[uk] - 1;
}
uk += 1;
}
if (go == -1){
return -1;
}
ans += 1;
pos = go;
}
return ans;
}
else{
return -1;
}
}
