#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5;
const int mxK = 1e5;
vector<int> who[mxK];
map<int, int> dp[mxN+1];
int minimumInstructions(int n, int m, int k,
vector<int> a, vector<int> g_sz, vector<vector<int>> g) {
for (int i = 0; i < m; ++i)
for (int j : g[i])
who[j].push_back(i);
vector<int> can;
for (int i = n-1; i >= 0; --i) {
for (int j : who[a[i]]) {
auto it = dp[i+1].find((j+1)%m);
int cnt = 1;
if (it != dp[i+1].end()) cnt += it->second;
dp[i].emplace(j, cnt);
if (cnt >= m) can.push_back(i);
}
}
reverse(can.begin(), can.end());
int i = 0, ans = 0;
while (i < n) {
auto it = upper_bound(can.begin(), can.end(), i);
if (it == can.begin()) break;
int ni = *(--it) + m;
if (ni <= i) break;
i = ni;
++ans;
}
if (i < n) return -1;
return ans;
}
