#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];
ordered_map<int, int> M[maxM], M_next[maxM];
int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
C.insert(C.begin(), -1);
A.insert(A.begin(), 0);
B.insert(B.begin(), vector<int>());
FOR(i, 1, m) {
for(int v : B[i]) {
Q[v].push_back(i);
M[i][v] = 1;
}
}
FOR(i, 1, k) {
for(int u : Q[i])
for(int v : Q[i]) M_next[u][v] = 1;
}
/// all about kmp
kmp[0] = -1;
FOR(i, 2, m) {
for(int j = kmp[i - 1]; j != -1; j = kmp[j]) {
if (M_next[i][j + 1]) {
kmp[i] = j + 1;
break;
}
}
}
prefix[0] = 0;
FOR(i, 1, n) {
for(int j = prefix[i - 1]; j != -1; j = kmp[j]) {
if (M[j + 1][C[i]]) {
prefix[i] = j + 1;
break;
}
}
}
kmp2[m + 1] = m + 2;
kmp2[m] = m + 1;
FORD(i, m - 1, 1) {
kmp2[i] = m + 1;
for(int j = kmp2[i + 1]; j != m + 2; j = kmp2[j]) {
if (M_next[i][j - 1]) {
kmp2[i] = j - 1;
break;
}
}
}
suffix[n + 1] = m + 1;
FORD(i, n, 1) {
suffix[i] = m + 1;
for(int j = suffix[i + 1]; j != m + 2; j = kmp2[j]) {
if (M[j - 1][C[i]]) {
suffix[i] = j - 1;
break;
}
}
}
/// build
FOR(i, 1, m) p[i][0] = kmp[i];
REP(j, 1, logM) FOR(i, 1, m) p[i][j] = p[p[i][j - 1]][j - 1];
/// solve
FOR(i, 1, m - 1) ans[i] = INF;
FOR(i, m, n) {
ans[i] = INF;
int vx = prefix[i];
int hope = suffix[i - m + 1] - 1;
REPD(j, logM, 0) if (p[vx][j] >= hope) vx = p[vx][j];
if (vx == hope) {
ans[i] = ans[i - m] + 1;
}
FORD(j, i - 1, i - m) {
if (ans[j] > ans[i]) ans[j] = ans[i];
else break;
}
}
if (ans[n] >= INF) ans[n] = -1;
return ans[n];
}
