#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
#include "paint.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 20;
const long double EPS = 1e-9, PI = acos(-1);
struct quemin
{
int l = 0, r = -1;
deque<pair<int, int>> q;
quemin() {}
void push_back(int x)
{
while (q.size() && q.back().first >= x)
{
q.pop_back();
}
r++;
q.push_back({ x, r });
}
void pop_front()
{
if (q.front().second == l)
{
q.pop_front();
}
l++;
}
int get()
{
return q.front().first;
}
};
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
int n = N, m = M, k = K;
vector<int> c = C, a = A;
vector<vector<int>> b = B;
vector<vector<int>> like(k);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < b[i].size(); j++)
{
like[b[i][j]].push_back(i);
}
}
vector<vector<int>> has(n);
for (int i = 0; i < n; i++)
{
has[i] = like[c[i]];
}
vector<vector<int>> tomx(n);
vector<pair<int, int>> nxt(m, { -1, -1 });
vector<int> pos0(n, -1);
for (int i = n - 1; i > -1; i--)
{
tomx[i].resize(has[i].size());
for (int j = 0; j < has[i].size(); j++)
{
tomx[i][j] = has[i][j];
if (has[i][j] == m - 1)
{
continue;
}
if (nxt[has[i][j] + 1].first == i + 1)
{
tomx[i][j] = tomx[nxt[has[i][j] + 1].first][nxt[has[i][j] + 1].second];
}
}
for (int j = 0; j < has[i].size(); j++)
{
if (has[i][j] == 0)
{
pos0[i] = j;
}
nxt[has[i][j]] = { i, j };
}
}
vector<bool> can(n);
for (int i = n - m; i > -1; i--)
{
for (int j = 0; j < has[i].size(); j++)
{
if (tomx[i][j] != m - 1)
{
continue;
}
if (has[i][j] != 0)
{
int to = i + (m - has[i][j]);
if (pos0[to] == -1)
{
continue;
}
if (tomx[to][pos0[to]] < has[i][j] - 1)
{
continue;
}
}
can[i] = true;
break;
}
}
vector<int> dp(n + 1, INF);
dp[n] = 0;
quemin qmn;
for (int i = 0; i < m; i++)
{
qmn.push_back(dp[n - i]);
}
for (int i = n - m; i > -1; i--)
{
if (can[i] && qmn.get() != INF)
{
dp[i] = 1 + qmn.get();
}
qmn.pop_front();
qmn.push_back(dp[i]);
}
return (dp[0] == INF ? -1 : dp[0]);
}
/*
int main()
{
int N, M, K;
assert(3 == scanf("%d %d %d", &N, &M, &K));
std::vector<int> C(N);
for (int i = 0; i < N; ++i)
{
assert(1 == scanf("%d", &C[i]));
}
std::vector<int> A(M);
std::vector<std::vector<int>> B(M);
for (int i = 0; i < M; ++i)
{
assert(1 == scanf("%d", &A[i]));
B[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j)
{
assert(1 == scanf("%d", &B[i][j]));
}
}
int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
printf("%d\n", minimum_instructions);
return 0;
}
*/
/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/
