#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
const int N = 1e5 + 5;
int n;
const int Inf = 0x3f3f3f3f;
struct SegmentTree {
int f[N * 2];
SegmentTree() {
memset(f, 0x3f, sizeof f);
}
void upd(int u, int x) {
++u;
for (f[u += n] = x; u > 1; u >>= 1)
f[u >> 1] = min(f[u], f[u ^ 1]);
}
int get(int l, int r) {
int ans = Inf;
++l; ++r;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = min(ans, f[l++]);
if (r & 1) ans = min(ans, f[--r]);
}
return ans;
}
};
SegmentTree St;
int ok[N];
vector<int> f[N];
set<int> lf[N], rf[N];
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
n = N + 1;
for (int i = 0; i < M; ++i)
sort(all(B[i]));
for (int i = 0; i < M; ++i) for (int u: B[i])
f[u].push_back(i);
for (int i = 1; i <= N; ++i) {
for (int u: lf[i - 1]) if (u + 1 < M) {
if (binary_search(all(B[u + 1]), C[i - 1]))
lf[i].insert(u + 1);
}
if (binary_search(all(B[0]), C[i - 1]))
lf[i].insert(0);
}
for (int i = N; i >= 1; --i) {
for (int u: rf[i + 1]) if (u > 0) {
if (binary_search(all(B[u - 1]), C[i - 1]))
rf[i].insert(u - 1);
}
if (binary_search(all(B[M - 1]), C[i - 1]))
rf[i].insert(M - 1);
}
for (int i = 1; i <= N; ++i) {
ok[i] = rf[i].find(0) != rf[i].end();
if (!ok[i]) {
for (int u: f[C[i - 1]]) if (u != 0) {
ok[i] |= (rf[i].find(u) != rf[i].end()) & (lf[i + M - 1].find(u - 1) != lf[i + M - 1].end());
if (ok[i]) break;
}
}
}
St.upd(0, 0);
for (int i = M; i <= N; ++i) if (ok[i - M + 1]) {
St.upd(i, St.get(i - M, i - 1) + 1);
}
int ans = St.get(N, N);
if (ans == Inf) ans = -1;
return ans;
}
