#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
int minimumInstructions(int n,int m,int q,vector<int> C,vector<int> A,vector<vector<int>> B){
multiset<int> M;
vector<vector<int>> D(q);
for (int i(0);i < m;++i) for (int k:B[i]) D[k].emplace_back(i);
vector<int> dp(m),E;
for (int i(n-1);i > -1;--i){
vector<int> F(D[C[i]].size());
for (int k(0);k < (int)F.size();++k) F[k] = dp[(D[C[i]][k]+1)%m]+1;
for (int a:E) dp[a] = 0;
for (int k(0);k < (int)F.size();++k) dp[D[C[i]][k]] = F[k];
E = D[C[i]];
if (!F.empty()&&*max_element(F.begin(),F.end())>=m) M.emplace(i);
}
int ret(0);
for (int i(0);i < n;){
if (M.empty()||*M.begin()>i) return -1;
int x = i;
while(!M.empty()&&*M.begin()<=i) x = *M.begin()+m,M.erase(M.begin());
i = x,++ret;
}
return ret;
}
