#include<bits/stdc++.h>
#include "paint.h"
#define MAXN 100007
using namespace std;
int n,m,k,ans;
int c[MAXN];
unordered_set<int> cols[MAXN];
vector<int> where[MAXN];
bool can[MAXN];
int to[2][MAXN];
int best[MAXN],pref[MAXN];
int li[MAXN],tim;
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 i=1;i<=n;i++){
c[i]=C[i-1];
}
for(int i=1;i<=m;i++){
for(int s:B[i-1]){
cols[i].insert(s);
where[s].push_back(i);
}
}
for(int i=n;i>=1;i--){
for(int f:where[c[i]]){
if(li[f+1]!=tim)to[1-i%2][f+1]=0;
if(li[1]!=tim)to[1-i%2][1]=0;
if(f<m)to[i%2][f]=to[1-i%2][f+1]+1;
else to[i%2][f]=to[1-i%2][1]+1;
if(to[i%2][f]>=m)best[i]=max(best[i],i+m);
li[f]=tim+1;
}
tim++;
}
for(int i=1;i<=n;i++){
pref[i]=max(pref[i-1],best[i]);
}
int pos=1;
while(pos<=n){
if(pref[pos]<=pos)return -1;
pos=pref[pos];
ans++;
}
return ans;
}
/*
int main(){
//cout<<minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}});
cout<<minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}});
return 0;
}
*/
