MIT Individual Contest 2007

In the set cover problem there is a collection C = {S₁, ...,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₀, ...,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].

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 ith group starts with one line containing |S_i|, the size of the ith 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
0

Output:
2
1 2