#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
const int MAXM = 50004;
vector<int> B[MAXM], C[MAXN];
int f[20004][2003];
int colNeed[MAXN], dp[MAXN], sum[MAXN], nArr, mArr, numCol;
bool dx[2003][MAXN], ok[MAXN];
int sub1(void) {
for (int i = 1; i <= nArr; ++i) {
if(sz(C[colNeed[i]]) == 0)
return -1;
dp[i] = C[colNeed[i]][0];
sum[i] = sum[i - 1] + (i > 1 && (dp[i - 1] + 1) % mArr == dp[i]);
}
int res(0), maxi(1), lastok(-mArr);
for (int i = 1; i <= nArr; ++i) {
if(sum[i + mArr - 1] - sum[i] == mArr - 1 && (dp[i + mArr - 1] + 1) % mArr == dp[i])
lastok = i;
if(i == maxi) {
if(lastok + mArr <= i)
return -1;
maxi = lastok + mArr;
++res;
}
}
return res;
}
int sub3(void) {
for (int j = 0; j < mArr; ++j) {
for (int it = 0; it < sz(B[j]); ++it)
dx[j][B[j][it]] = 1;
}
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
ok[i] = 0;
for (int j = 0; j < mArr; ++j) {
ok[i] = 1;
for (int k = 0; k < mArr; ++k)
ok[i] &= (dx[(j + k) % mArr][colNeed[i + k]]);
if(ok[i])
break;
}
}
dp[0] = 0;
for (int i = 1; i <= nArr; ++i)
dp[i] = 1e9+7;
for (int i = 0; i < nArr; ++i) {
for (int j = 0; i + 1 - j > 0 && j < mArr; ++j) {
if(ok[i + 1 - j])
dp[i + mArr - j] = min(dp[i + mArr - j], dp[i] + 1);
}
}
return (dp[nArr] >= 1e9) ? -1 : dp[nArr];
}
int sub4(void) {
for (int j = 0; j < mArr; ++j) {
for (int it = 0; it < sz(B[j]); ++it)
dx[j][B[j][it]] = 1;
}
for (int i = nArr; i > 0; --i) {
for (int j = mArr; j > 0; --j)
f[i][j] = f[i + 1][j + 1] + (dx[j - 1][colNeed[i]]);
}
for (int i = 1; i + mArr - 1 <= nArr; ++i) {
for (int j = 0; j < mArr; ++j) {
ok[i] = (f[i][j + 1] + f[i + mArr - j][1] - f[i + mArr][j + 1] == mArr);
if(ok[i])
break;
}
}
dp[0] = 0;
for (int i = 1; i <= nArr; ++i)
dp[i] = 1e9+7;
for (int i = 0; i < nArr; ++i) {
for (int j = 0; i + 1 - j > 0 && j < mArr; ++j) {
if(ok[i + 1 - j])
dp[i + mArr - j] = min(dp[i + mArr - j], dp[i] + 1);
}
}
return (dp[nArr] >= 1e9) ? -1 : dp[nArr];
}
int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
nArr = _N, mArr = _M, numCol = _K;
for (int i = 1; i <= nArr; ++i) {
colNeed[i] = _C[i - 1];
C[i].clear();
}
int maxf(0);
for (int i = 0; i < mArr; ++i) {
int szlike(_A[i]);
B[i].clear();
for (int j = 0; j < szlike; ++j) {
B[i].push_back(_B[i][j]);
C[_B[i][j]].push_back(i);
maxf = max(maxf, sz(C[_B[i][j]]));
}
}
if(maxf <= 1)
return sub1();
if(nArr <= 500)
return sub3();
if(nArr <= 20000 && mArr <= 2000)
return sub4();
return -1;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "paint"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _A, _C;
vector<vector<int>> _B;
int _N, _M, _K;
cin >> _N >> _M >> _K;
_C.resize(_N);
for (int i = 0; i < _N; ++i) {
cin >> _C[i];
_C[i] = Random(0, _K - 1); cout << _C[i] << " \n"[i + 1 == _N];
}
vector<int> col; for (int i = 0; i < _K; ++i) col.push_back(i);
_A.resize(_M), _B.resize(_M);
for (int i = 0; i < _M; ++i) {
cin >> _A[i];
_A[i] = Random(1, _K); cout << _A[i] << ' ';
_B[i].resize(_A[i]);
shuffle(col.begin(), col.end(), rng);
for (int j = 0; j < _A[i]; ++j) {
cin >> _B[i][j];
_B[i][j] = col[j]; cout << _B[i][j] << " \n"[j + 1 == _A[i]];
}
}
int ans = minimumInstructions(_N, _M, _K, _C, _A, _B);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
