#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int lseg1[200100], lseg2[200100];
vector<int> liked_by[200100];
int dp[200100]{}, valid_i[200100]{};
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
for(int i = 0; i < K; i++) liked_by[i].clear();
multiset<int> st;
for(int i = 0; i < M; i++)
for(int color: B[i])
liked_by[color].push_back(i);
for(int i = N; i--;) {
for(auto j: liked_by[C[i]]) {
lseg1[j] = 1+lseg2[(j+1)%M];
if(lseg1[j]>=M) valid_i[i]=1;
}
swap(lseg1, lseg2);
if(i<N-1)
for(auto j:liked_by[C[i+1]])
lseg1[j]=0;
}
for(int i = 0; i < M; i++) st.insert(0);
for(int i = N; i--;) {
dp[i]=1e9;
if(valid_i[i])
dp[i] = 1+*st.begin();
st.insert(dp[i]);
st.erase(st.find(dp[i+M]));
}
return (dp[0]<1e9?dp[0]:-1);
}
