Minimum Painting Instructions

Pak Dengklek wants to repaint his wall. The wall consists of \(N\) segments numbered from \(0\) to \(N-1\), and there are \(K\) different colors available, represented by integers from \(0\) to \(K-1\). Pak Dengklek wishes to paint segment \(i\) with color \(C[i]\).

He hires a contracting company that has \(M\) contractors numbered \(0\) to \(M-1\). Unfortunately, each contractor only wants to paint using his preferred colors. Specifically, contractor \(j\) likes \(A[j]\) colors and is only willing to paint with one of these colors: \(B[j][0], B[j][1], \dots, B[j][A[j]-1]\).

Pak Dengklek can issue instructions to the contracting company. In a single instruction, he gives two parameters \(x\) and \(y\) (with \(0 \le x < M\) and \(0 \le y \le N-M\)). The company will assign contractor \((x+l) \bmod M\) to paint segment \(y+l\) for every \(0 \le l < M\). An instruction is valid if for every \(0 \le l < M\), contractor \((x+l) \bmod M\) likes the desired color \(C[y+l]\) for that segment. If there exists any \(l\) for which the assigned contractor does not like the color \(C[y+l]\), the instruction is invalid. Note that a segment can be painted multiple times as long as every paint is in Pak Dengklek's desired color.

Your task is to implement the function minimumInstructions(N, M, K, C, A, B) which returns the minimum number of valid instructions needed so that every segment \(0 \le i < N\) eventually gets painted with its desired color. If it is impossible, return \(-1\).

The process can be modeled as covering the segments \([0, N-1]\) with intervals of length \(M\) (each instruction covers segments \([y, y+M-1]\) if valid) using a minimum number of intervals (instructions). Use a greedy strategy to cover the entire wall.

Function Signature: minimumInstructions(N, M, K, C, A, B)

Constraints:

• \(1 \le N \le 10^5\) (number of wall segments)
• \(1 \le M \le N\) (number of contractors)
• \(1 \le K \le 10^5\) (number of colors)
• \(0 \le C[i] < K\) for each \(i\).
• For each contractor \(j\), \(1 \le A[j] \le K\) and \(B[j] contains A[j] distinct integers in the range \([0, K-1]\).

Input/Output Note: The input is read from standard input and the output should be the single integer answer.

inputFormat

The first line contains three integers: \(N\), \(M\), and \(K\).

The second line contains \(N\) space-separated integers representing the array \(C\) (the desired color for each segment).

The third line contains \(M\) space-separated integers representing the array \(A\) (the number of colors each contractor likes).

Then follow \(M\) lines, where the \(j\)-th line contains \(A[j]\) space-separated integers denoting the array \(B[j]\) (the colors contractor \(j\) likes).

outputFormat

Output a single integer: the minimum number of valid instructions needed to cover all segments with the desired colors, or \(-1\) if it is impossible.

sample

5 2 3
0 1 0 1 0
2 2
0 1
0 1

3