#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int N = 1e5+10;
const int INF = 1e9;
const int K = 1e5+10;
int ans[N], n, m, k;
vector<int> cl[N];
int len[2][K+1];
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
for (int i=0; i<m; ++i) {
for (auto u : b[i]) cl[u].push_back(i), cl[u].push_back(i+m);
}
if (n == 1) {
bool ok=false;
for (auto u : b[0]) ok |= (u == c[0]);
if (ok) return 1;
return -1;
}
for (int i=0; i<m-1; ++i) ans[i]=INF;
for (auto u : cl[c[0]]) len[0][u]=1;
if (m == 1 && len[0][c[0]] >= 1) ans[0]=1;
else ans[0]=INF;
multiset<int> ms; ms.insert(ans[0]);
for (int i=1; i<n; ++i) {
int mx=0;
int l=(i-1)&1, r=i&1;
for (auto u : cl[c[i]]) {
if (len[l][u-1] == 0) len[r][u]=1;
else len[r][u]=len[l][u-1]+1;
mx=max(mx, len[r][u]);
}
if (mx >= m) ans[i]=(*ms.begin())+1;
else ans[i]=INF;
if (mx >= m && i == m-1) ans[i]=1;
if (i-m >= 0) ms.erase(ms.find(ans[i-m]));
ms.insert(ans[i]);
for (auto u : cl[c[i-1]]) len[l][u]=0;
}
if (ans[n-1] >= INF) return -1;
return ans[n-1];
}
