#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, mx=5e4+5, kx=1e5+5;
int dp[mx], mn[nx];
vector<int> g[kx];
vector<pair<int, int>> pv;
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<M; i++) dp[i]=-1;
for (int i=0; i<N; i++)
{
vector<pair<int, int>> nw;
mn[i]=1e9;
for (auto idx:g[C[i]])
{
if (dp[(idx-1+M)%M]==1e9) nw.push_back({idx, i}), mn[i]=min(mn[i], i);
else nw.push_back({idx, dp[(idx-1+M)%M]}), mn[i]=min(mn[i], dp[(idx-1+M)%M]);
}
for (auto [idx, x]:pv) dp[idx]=1e9;
for (auto [idx, x]:nw) dp[idx]=x;
pv=nw;
}
int l=M-1, r=M-1, ans=0;
while (l<N)
{
for (int i=r; i>=l; i--)
{
if (mn[i]<=i-M+1)
{
l=i+1, r=i+M, ans++;
break;
}
if (i==l) return -1;
}
}
return ans;
}
