#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int N, int M, int K, vector<int> colors, vector<int> num, vector<vector<int> > B) {
/*
Idea:
1. Check for all contractors who like to color colors[N - 1];
2. Traverse backwards, and update values of contractors
3. suffix[contractor X] = Y means that X paints Y, X + 1 paints Y + 1 and so on.
*/
auto begin = std::chrono::high_resolution_clock::now();
set<pair<int, int> > Matches; //contractor, color;
for(int i = 0; i < M; i++) {
for(int j = 0; j < num[i]; j++) {
Matches.insert(make_pair(i, B[i][j]));
}
}
vector<int> LastColorLike, FirstColorLike;
for(int i = 0; i < N; i++) {
if(Matches.count(make_pair(M - 1, colors[i]))) {
LastColorLike.push_back(i);
}
if(Matches.count(make_pair(0, colors[i]))) {
FirstColorLike.push_back(i);
}
}
//auto end = std::chrono::high_resolution_clock::now();
//auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//assert((elapsed.count() * 1e-9) < 1500);
//LastColorLike stuff ------------------------------------------------------------
set<int> suffixLiking[M];
//set<int> AlreadyTaken[M];
for(int colorIdx: LastColorLike) {
//cout << "colorIdx = " << colorIdx << "\n";
int curContractor = M - 1;
if(!suffixLiking[curContractor].count(colorIdx)) {
suffixLiking[curContractor].insert(colorIdx);
//AlreadyTaken[curContractor].insert(colorIdx);
}
else {
break;
}
for(int i = curContractor - 1; i >= 0; i--) {
colorIdx--;
//cout << "i = " << i << ", colorIdx = " << colorIdx << "\n";
if(colorIdx < 0) {
break;
}
if(Matches.count({i, colors[colorIdx]})) {
if(!suffixLiking[i].count(colorIdx)) {
//AlreadyTaken[i].insert(colorIdx);
suffixLiking[i].insert(colorIdx);
}
else {
break;
}
}
else {
break;
}
}
}
//auto end = std::chrono::high_resolution_clock::now();
//auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//assert((elapsed.count() * 1e-9) < 1500);
/*for(int i = 0; i < M; i++) {
for(auto j: suffixLiking[i]) {
cout << "i = " << i << ", suffix = " << j << "\n";
}
cout << "\n\n";
}*/
//--------------------------------------------------------------------------------
//FirstColorLike stuff -----------------------------------------------------------
set<int> prefixLiking[M];
for(int colorIdx: FirstColorLike) {
int curContractor = 0;
if(!prefixLiking[curContractor].count(colorIdx)) {
prefixLiking[curContractor].insert(colorIdx);
}
else {
break;
}
for(int i = 1; i < M; i++) {
colorIdx++;
if(colorIdx >= N) {
break;
}
if(Matches.count({i, colors[colorIdx]})) {
if(!prefixLiking[i].count(colorIdx)) {
prefixLiking[i].insert(colorIdx);
}
else {
break;
}
}
else {
break;
}
}
}
//auto end = std::chrono::high_resolution_clock::now();
//auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//assert((elapsed.count() * 1e-9) < 1500);
/*for(int i = 0; i < M; i++) {
for(auto j: prefixLiking[i]) {
cout << "i = " << i << ", prefix = " << j << "\n";
}
cout << "\n\n";
}*/
//--------------------------------------------------------------------------------
set<int> specificPrefix[N], specificSuffix[N];
for(int i = 0; i < M; i++) {
for(auto j: prefixLiking[i]) {
specificPrefix[j].insert(i);
}
for(auto j: suffixLiking[i]) {
specificSuffix[j].insert(i);
}
}
int furthestTaken = 0, ans = 0;
set<int> alreadyVisited;
while(furthestTaken != N) {
//cout << "furthestTaken = " << furthestTaken << "\n";
int curColorIdx = furthestTaken;
while(curColorIdx >= 0 && curColorIdx >= furthestTaken - M) {
//cout << "curColorIdx = " << curColorIdx << "\n";
if(alreadyVisited.count(curColorIdx) || N - curColorIdx < M) {
curColorIdx--;
continue;
}
//cout << "continued\n";
int f = 0;
alreadyVisited.insert(curColorIdx);
for(auto i: specificSuffix[curColorIdx]) {
int curIdx = i;
if(curIdx == 0) {
f = 1;
furthestTaken = curColorIdx + M;
ans++;
break;
}
int prefixIdx = curIdx - 1;
int added = curColorIdx + M - 1;
if(specificPrefix[added].count(prefixIdx)) {
f = 1;
furthestTaken = curColorIdx + M;
ans++;
break;
}
}
//cout << "f = " << f << "\n";
if(f == 1) {
break;
}
curColorIdx--;
}
if(curColorIdx < 0 || curColorIdx < furthestTaken - M) {
ans = -1;
break;
}
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
assert((elapsed.count() * 1e-9) < 1500);
return ans;
}
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}*/
