SP1965 SETCOV - Set Cover

In the set cover problem there is a collection _C = {S $ _{1} $ , ...,S $ _{m} $ }_ of subsets of the universe \[_n_\] = _{0, ...,n-1}_, and one must find a minimum-sized subcollection of _C_ that still covers \[_n_\] (it may be the case that _S $ _{i} $_ and _S $ _{j} $_ contain the exact same elements for some _i_ ≠ _j_). A **path of length r** is a graph on _r+1_ vertices _v $ _{0} $ , ...,v $ _{r} $_ where _v $ _{i} $_ has an undirected edge to _v $ _{i+1} $_ for _i = 0, ...,r-1_ (these are the only edges). A set cover instance _I_ is said to be **path-realizable** if there exists a mapping from _I_ to a path of length _m_ where the _S $ _{i} $_ are mapped to edges in the path and each _i_ in \[_n_\] is mapped to a pair of (not-necessarily distinct) vertices _s $ _{i} $_ , _t $ _{i} $_ on the path such that the edges lying between _s $ _{i} $_ and _t $ _{i} $_ correspond exactly to the sets of _C_ that contain _i_. Two sets _S $ _{i} $ ,S $ _{j} $_ must be mapped to different edges on the path if _i_ ≠ _j_. You will be given a set cover instance that is guaranteed to be path-realizable and should output the size of a minimum-sized subcollection of _C_ still covering \[_n_\].

The first line of the input is "_N M_" (_1_ ≤ N, M ≤ 300), where _N_ is the size of the universe and _M_ is the number of sets _S $ _{i} $_ in the collection of subsets of _{0, ...,N - 1}_. What follows are _M_ groups of lines. The _i_th group starts with one line containing |_S $ _{i} $_ |, the size of the _i_th subset. If |_S $ _{i} $_ | = 0, the current group of lines ends. Otherwise the next line is a space-separated list of the elements contained in _S $ _{i} $_ .

If \[_n_\] cannot be covered by a subcollection of _C_ then you should output _-1_, followed by a newline. Otherwise, your output should consist of two lines. The first line is the size of a minimum-sized set cover. The second line is a space-separated list of the 0-based indices of the sets in an optimal set cover.