Minimum Candy Package Selection

You are given a candy store that sells candies of M different flavors, numbered from \(1\) to \(M\). The candies are only sold in packages of K candies. Each package lists the flavors of its K candies, so you know exactly which flavors are contained in each package before purchase.

Xiaoming wants to try every flavor in the store. Given N packages, determine the minimum number of packages he must buy so that he can taste all \(M\) flavors.

If it is impossible to obtain all flavors with the given packages, you should output -1.

The relationship can be described mathematically as follows: Let each package \(i\) provide a set of flavors \(S_i \subseteq \{1, 2, \ldots, M\}\). Find the smallest integer \(t\) and a collection of indices \(i_1, i_2, \ldots, i_t\) such that:

[ S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_t} = {1, 2, \ldots, M} ]

inputFormat

The first line contains three integers: \(M\), \(K\), and \(N\), where \(M\) is the number of candy flavors, \(K\) is the number of candies per package, and \(N\) is the number of packages available.

Each of the next \(N\) lines contains \(K\) integers. The \(i\)-th line indicates the flavors contained in the \(i\)-th package.

outputFormat

Output a single integer: the minimum number of packages needed so that the union of their flavors is \(\{1, 2, \ldots, M\}\). If it is impossible to get all flavors, output -1.

sample

3 2 3
1 2
2 3
1 3

2