#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
const int INF = 2e9;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
int toR[2][M];
deque<int> q = {N};
vector<int> cand[K], dp(N+1, INF);
dp[N] = 0;
for(int i : {0, 1})
fill(toR[i], toR[i] + M, 0);
for(int i = 0; i < M; i++)
for(int &j : B[i])
cand[j].push_back(i);
for(int i = N; --i >= 0; ) {
if(!empty(q) && q.front() > i + M) q.pop_front();
bool ok = 0;
for(int j : cand[C[i]])
if((toR[i & 1][j] = 1 + toR[!(i & 1)][(j + 1) % M]) >= M)
ok = 1;
if(ok && !empty(q)) {
dp[i] = 1 + dp[q.front()];
while(!empty(q) && dp[i] <= dp[q.back()])
q.pop_back();
q.push_back(i);
}
if(i + 1 < N)
for(int j : cand[C[i+1]])
toR[!(i & 1)][j] = 0;
}
return dp[0] == INF ? -1 : dp[0];
}
