#include "paint.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef pair<int, int> ii;
const int maxN = 100000;
const int maxK = 100000;
const int maxM = 50000;
const int maxfK = 632;
int n, m, k, c[maxN];
vector <int> hasColor[maxK];
bool mark[maxN];
int nF[2];
ii f[2][maxfK], g[maxM];
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;
k = K;
for(int i = 0; i < n; i++)
c[i] = C[i];
for(int i = 0; i < m; i++)
for(int col : B[i])
hasColor[col].push_back(i);
for(int i = 0; i < n; i++){
int id = i & 1;
for(int j = 0; j < nF[id ^ 1]; j++)
g[f[id ^ 1][j].X] = mp(i, f[id ^ 1][j].Y);
nF[id] = 0;
for(int x : hasColor[c[i]]){
int pre = (x + m - 1) % m;
if (g[pre].X == i)
f[id][nF[id]++] = mp(x, g[pre].Y + 1);
else
f[id][nF[id]++] = mp(x, 1);
if (f[id][nF[id] - 1].Y >= m)
mark[i - m + 1] = 1;
}
}
int cur = -1, best = -1, res = 0;
for(int i = 0; i < n; i++){
if (mark[i])
best = i + m - 1;
if (cur < i){
res++;
cur = best;
}
if (cur < i)
return -1;
}
return res;
}
