#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
using namespace __gnu_pbds;
template <class key, class value>
using ordered_map = tree<key, value, less<key>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 100005, maxM = 50005, logM = 16, maxK = 100005, INF = 0x3c3c3c3c;
int kmp[maxM], kmp2[maxM], prefix[N], suffix[N], ans[N];
int p[maxM][logM];
vector<int> Q[maxK];
map<int, int> M[maxM], M_next[maxM];
int avail[N], num[N], maxL[N];
int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
C.insert(C.begin(), -1);
FOR(i, 1, m) {
for(int v : B[i - 1]) {
Q[v].push_back(i);
}
}
vector<pair<int, int>> List;
FOR(i, 1, n) {
for(int v : Q[C[i]]) {
if (avail[(v == 1 ? m : v - 1)] == i - 1) {
List.emplace_back(v, num[(v == 1 ? m : v - 1)] + 1);
}
else {
List.emplace_back(v, 1);
}
}
for(auto [v, val] : List) {
avail[v] = i;
num[v] = val;
maxL[i] = max(maxL[i], val);
}
List.clear();
}
deque<int> DQ;
DQ.push_back(0);
FOR(i, m, n) {
while (!DQ.empty() && DQ.front() < i - m) DQ.pop_front();
if (DQ.empty()) return -1;
if (maxL[i] >= m) ans[i] = ans[DQ.front()] + 1, DQ.push_back(i);
}
if (ans[n] == 0) return -1;
return ans[n];
}
