#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "paint.h"
//#include "grader.cpp"
int P[400005][20];
int minimumInstructions(int n,int m, int K,vector<int> a,vector<int> sz,vector<vector<int>> b) {
    vector<vector<int>> idx_color(K);
    for(int i=0;i<m;i++){
        for(auto j : b[i]) idx_color[j].push_back(i);
    }
    vector<vector<int>> v(n);
    for(int i=0;i<n;i++) {
        v[i] = idx_color[a[i]];
    }
    int pt = 1;
    vector<vector<int>> id(n);
    for(int i=0;i<n;i++){
        for(auto j : v[i]) id[i].push_back(pt) , pt ++;
    }
    for(int i=0;i<n-1;i++){
        map<int,int> exist;
        for(int j=0;j<(int)v[i].size();j++) exist[v[i][j]] = id[i][j];
        for(int j=0;j<(int)v[i+1].size();j++){
            if(exist.count((v[i+1][j]-1+m)%m)) {
                int node = exist[(v[i+1][j]-1+m)%m];
                P[node][0] = id[i+1][j];
            }
        }
    }
    for(int k=1;k<20;k++){
        for(int i=0;i<pt;i++){
            P[i][k] = P[P[i][k-1]][k-1];
        }
    }
    vector<bool> valid(n);
    for(int i=n-1;i>=0;i--){
        for(auto j : id[i]){
            int req = m - 1;
            int node = j;
            for(int k=0;k<20;k++){
                if((1<<k)&req){
                    node = P[node][k];
                }
            }
            if(node == 0) continue;
            valid[i] = 1;
            break;
        }
    }
    vector<int> dp(n+1,1e9);
    dp[n] = 0;
    deque<int> dq;
    dq.push_back(n);
    for(int i=n-1;i>=0;i--){
        while(dq.size() && dq.front() > i + m) dq.pop_front();
        if(valid[i]) {
            if(dq.empty()) continue;
            dp[i] = dp[dq.front()] + 1;
            while(dq.size() && dp[dq.back()] >= dp[i]) dq.pop_back();
            dq.push_back(i);
        }
    }
    if(dp[0] == 1e9) return -1;
    return dp[0];
}