#include "bits/stdc++.h"
#include "paint.h"
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9;
vector <int> col[maxn];
int opt[2][maxn];
int c[maxn];
int n, m;
bool good[maxn];
int dp[maxn];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
n = N;
m = M;
for(int i = 0; i < n; i++) {
c[i] = C[i];
}
for(int i = 0; i < m; i++) {
for(int j : B[i]) {
col[j].push_back(i);
}
}
int row = 0;
for(int i = n - 1; i >= 0; i--) {
good[i] = false;
row ^= 1;
for(int j : col[c[i]]) {
opt[row][j] = opt[row ^ 1][(j + 1) % m] + 1;
if(opt[row][j] >= m) good[i] = true;
}
if(i < n - 1) {
for(int j : col[c[i + 1]]) {
opt[row ^ 1][j] = 0;
}
}
}
for(int i = 0; i < n; i++) dp[i] = inf;
dp[n] = 0;
deque <pair <int, int>> Q;
Q.push_front(make_pair(dp[n], n));
for(int i = n; i >= 0; i--) {
while(!Q.empty() && Q.back().second > i + m) {
Q.pop_back();
}
if(good[i]) {
dp[i] = 1 + Q.back().first;
}
while(!Q.empty() && Q.front().first >= dp[i]) {
Q.pop_front();
}
Q.push_front(make_pair(dp[i], i));
}
return dp[0] >= inf ? -1 : dp[0];
}
