#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 100005;
int dp[nx], mn[nx];
vector<pair<int,int>> pv;
vector<int> g[nx];
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
for (int i = 0; i < N; i++) mn[i] = 1e9;
for (int i = 0; i < M; i++) for (auto x : B[i]) g[x].emplace_back(i);
for (int i = 0; i < M; i++) dp[i] = 1e9;
for (int i = 0; i < N; i++) {
vector<pair<int,int>> nw;
for (auto idx : g[C[i]]) {
if (dp[(idx-1+M)%M] == 1e9) {
nw.emplace_back(idx, i);
mn[i] = min(mn[i], i);
} else {
nw.emplace_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;
}
