#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=100005,MAXM=50005;
bool ada[MAXN];
int terakhir[MAXN];
bitset<MAXN> wrn[MAXM];
vector<int> F[MAXN],now,prv;
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 isi : B[i]){
F[isi].push_back(i);
wrn[i][isi]=true;
}
}
now.resize(M);prv.resize(M);
for(auto isi : F[C[N-1]]){
prv[isi]=N-1;
if(prv[isi]>=N-1+M-1)ada[N-1]=true;
}
for(int i=N-2;i>=0;i--){
for(auto isi : F[C[i]]){
if(wrn[(isi+1)%M][C[i+1]]){
now[isi]=prv[(isi+1)%M];
}
else{
now[isi]=i;
}
if(now[isi]>=i+M-1)ada[i]=true;
}
now.swap(prv);
}
int lastnyala=-1;
for(int i=0;i<N;i++){
if(ada[i])lastnyala=i;
terakhir[i]=lastnyala;
}
if(!ada[0])return -1;
int cover=M-1,ans=1,last=0;
while(cover!=N-1){
int i=terakhir[cover+1];
if(i>=last+1){
cover=i+M-1;
last=i;
ans++;
}
else return -1;
}
return ans;
}
