#include <bits/stdc++.h>
//#include "paint.h"
using namespace std;
#define pb push_back
#define mp make_pair
vector<int> adj[100001];
bool works[100001];
int dp[100001],curtot;
deque<int> num; //numi starts with i
int minimumInstructions(int n,int m,int k,vector<int> arr,vector<int> A,vector<vector<int> > B){
for (int i=0;i<m;i++){
for (int j=0;j<A[i];j++){
adj[B[i][j]].pb(i);
}
num.pb(0);
}
for (int i=0;i<m;i++){
for (auto j:adj[arr[i]]){
num[(j-i+m)%m]++;
}
}
for (int i=0;i<m;i++){
if (num[i]==m) curtot++;
}
if (curtot>0) works[0]=true;
for (int i=0;i<n-m;i++){
for (auto j:adj[arr[i]]){
if (num[j]==m) curtot--;
num[j]--;
}
for (auto j:adj[arr[i+m]]){
num[j]++;
if (num[j]==m) curtot++;
}
num.push_front(num.back());
num.pop_back();
if (curtot>0) works[i+1]=true;
//if (works[i]) cout<<i<<'\n';
}
for (int i=1;i<=n;i++){
dp[i]=1e9;
}
deque<pair<int,int> > dq;
dq.pb(mp(0,0));
for (int i=m;i<=n;i++){
if (!works[i-m]) continue;
while (!dq.empty() && dq[0].second<i-m){
dq.pop_front();
}
if (dq.empty()) return -1;
dp[i]=dq[0].first+1;
while (!dq.empty() && dq.back().first>=dp[i]){
dq.pop_back();
}
dq.pb(mp(dp[i],i));
}
if (dp[n]==1e9) return -1;
return dp[n];
}
