#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e4+5, mx=2e3+5, kx=1e5+5;
int dp[2][mx], mn[nx];
vector<int> g[kx];
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
for (int i=0; i<M; i++) for (auto x:B[i]) g[x].push_back(i);
for (int i=0; i<N; i++)
{
int c=i%2, p=1-c;
for (int j=0; j<M; j++) dp[c][j]=i+1;
for (auto idx:g[C[i]])
{
if (i==0) dp[c][idx]=i;
else dp[c][idx]=max(i-M+1, dp[p][(idx-1+M)%M]);
}
mn[i]=1e9;
for (int j=0; j<M; j++) mn[i]=min(mn[i], dp[c][j]);
//cout<<"here "<<i<<' '<<mn[i]<<'\n';
}
int cur=-1, lst=-2, ans=0;
while (cur!=N-1)
{
int f=0;
//cout<<"loop "<<cur<<' '<<lst<<'\n';
for (int i=cur; i>lst; i--)
{
if (mn[i+M]==i+1)
{
f=1;
lst=i;
ans++;
cur=i+M;
break;
}
}
if (!f) return -1;
}
return ans;
}
