#pragma GCC optimize("Ofast")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5;
const int mxK = 1e5;
vector<int> who[mxK+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);
a.push_back(k);
vector<int> can, dp(m), ndp(m);
for (int i = n-1; i >= 0; --i) {
for (int j : who[a[i]]) {
ndp[j] = dp[(j+1)%m] + 1;
if (ndp[j] >= m) can.push_back(i);
}
swap(dp, ndp);
for (int j : who[a[i+1]])
ndp[j] = 0;
}
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;
}
