#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A,vector<vector<int>> B){
vector < int > g[K] , d[N];
for(int i = 0; i < M; i++){
for(int j = 0; j < A[i]; j++){
// cout << i << ' ' << B[i][j] << '\n';
g[B[i][j]].push_back(i);
}
}
vector < pair < int , int > > v;
map < int , int > last[2];
for(int i = 0; i < N; i++){
last[i & 1].clear();
for(int it : g[C[i]]){
int prev = it - 1;
if(prev == -1) prev = M - 1;
if(!last[(i & 1) ^ 1].count(prev)) last[i & 1][it] = i - 1;
else last[i & 1][it] = last[(i & 1) ^ 1][prev];
if(last[i & 1][it] + M <= i){
d[i - M + 1].push_back(i + 1);
// cout << i - M + 1 << ' ' << i << '\n';
}
// cout << i << ' ' << it << ' ' << prev << ' ' << last[i & 1][it] << ' ' << last[i & 1][it] + M - 1 << '\n';
}
}
int dst[N + 1];
for(int i = 1; i <= N; i++){
dst[i] = 1e9;
d[i].push_back(i - 1);
}
dst[0] = 0;
queue < int > q;
q.push(0);
while(q.size() > 0){
int v = q.front();
q.pop();
for(int to : d[v]){
if(to == v - 1){
if(dst[to] > dst[v]){
dst[to] = dst[v];
q.push(to);
}
}
else{
if(dst[to] > dst[v] + 1){
dst[to] = dst[v] + 1;
q.push(to);
}
}
}
}
if(dst[N] == 1e9) return -1;
return dst[N];
}
// int main(){
// int N , M , K;
// cin >> N >> M >> K;
// vector < int > C(N);
// for(int i = 0; i < N; i++){
// cin >> C[i];
// }
// vector < int > A(M);
// vector < vector < int > > B(M);
// for(int i = 0; i < M; i++){
// cin >> A[i];
// for(int j = 0; j < A[i]; j++){
// int x;
// cin >> x;
// B[i].push_back(x);
// }
// }
// cout << minimumInstructions(N , M , K , C , A , B);
// }
