#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<vector<int>> who(K);
for (int i = 0; i < M; i += 1) {
for (auto j : B[i]) {
who[j].push_back(i);
}
}
vector<vector<int>> dp(N);
for (int i = 0; i < N; i += 1) {
dp[i].resize(who[C[i]].size());
}
for (int i = 0; i < who[C[N - 1]].size(); i += 1) {
dp[N - 1][i] = 1;
}
for (int i = N - 2; i >= 0; i -= 1) {
int ptr = 0;
for (int j = 0; j < who[C[i]].size(); j += 1) {
dp[i][j] = 1;
while (ptr < who[C[i + 1]].size() && who[C[i + 1]][ptr] <= who[C[i]][j]) {
ptr += 1;
}
if (ptr < who[C[i + 1]].size() && who[C[i + 1]][ptr] == (who[C[i]][j] + 1) % M) {
dp[i][j] = dp[i + 1][ptr] + 1;
}
if (who[C[i]][j] == M - 1 && who[C[i + 1]].size() > 0 && who[C[i + 1]][0] == 0) {
dp[i][j] = dp[i + 1][0] + 1;
}
}
}
vector<int> longest(N);
for (int i = 0; i < N; i += 1) {
for (int j = 0; j < who[C[i]].size(); j += 1) {
longest[i] = max(longest[i], dp[i][j]);
}
}
vector<int> sol(N, 1e9);
sol[N - M] = (longest[N - M] >= M ? 1 : 1e9);
for (int i = N - M - 1; i >= 0; i -= 1) {
if (longest[i] >= M) {
for (int j = i; j <= i + M - 1; j += 1) {
sol[i] = min(sol[i], sol[j + 1] + 1);
}
}
}
if (sol[0] == 1e9) {
return -1;
}
return sol[0];
}
/**
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int N, M, K;
cin >> N >> M >> K;
vector<int> C(N);
for (int i = 0; i < N; i += 1) {
cin >> C[i];
}
vector<int> A(M);
vector<vector<int>> B(M);
for (int i = 0; i < M; i += 1) {
cin >> A[i];
B[i].resize(A[i]);
for (int j = 0; j < A[i]; j += 1) {
cin >> B[i][j];
}
}
cout << minimumInstructions(N, M, K, C, A, B);
return 0;
}
**/
/**
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
**/
