Submit | All submissions | Best solutions | Back to list |

## 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*and

_{i}*S*contain the exact same elements for some

_{j}*i*≠

*j*). A

**path of length r**is a graph on

*r+1*vertices

*v*where

_{0}, ...,v_{r}*v*has an undirected edge to

_{i}*v*for

_{i+1}*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*are mapped to edges in the path and each

_{i}*i*in [

*n*] is mapped to a pair of (not-necessarily distinct) vertices

*s*,

_{i}*t*on the path such that the edges lying between

_{i}*s*and

_{i}*t*correspond exactly to the sets of

_{i}*C*that contain

*i*. Two sets

*S*must be mapped to different edges on the path if

_{i},S_{j}*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*].

### Input

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*|, the size of the

_{i}*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}### Output

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.

### Example

Input:3 4 0 2 2 1 2 1 0 0Output:2 1 2

Added by: | Minilek |

Date: | 2007-10-25 |

Time limit: | 1.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |

Resource: | MIT Individual Contest 2007 |