#include "paint.h"
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e5+10;
vector<int> wrks[maxn];
int dp[2][maxn];
bool cann[maxn];
int lcnn[maxn];
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
for(int i = 0; i < M; i++)
for(int c: B[i])
wrks[c].push_back(i);
bool f = !(N&1);
for(int j: wrks[C[N-1]])
{
dp[f][j] = 1;
if(dp[f][j] == M)
cann[N-1] = true;
}
for(int i = N-2; i >= 0; i--)
{
f = !f;
int p = 0;
int cn = C[i+1];
int cs = wrks[cn].size();
for(int j: wrks[C[i]])
{
dp[f][j] = 1;
while(p < cs and wrks[cn][p] <= j)
p++;
if(j == M-1 and !wrks[cn].empty() and wrks[cn][0] == 0)
dp[f][j] += dp[!f][0];
else if(p < cs and wrks[cn][p] == j+1)
dp[f][j] += dp[!f][j+1];
dp[f][j] = min(M, dp[f][j]);
if(dp[f][j] == M)
cann[i] = true;
}
}
//for(int i = 0; i < N; i++) cerr << cann[i]; cerr << endl;
int lc = -1;
for(int i = 0; i < N; i++)
{
if(cann[i])
lc = i;
lcnn[i] = lc;
}
int p = 0;
int t = 0;
while(p < N)
{
int r = lcnn[p];
if(r == -1 or r+M == p)
return -1;
p = r+M;
t++;
}
return t;
}
