# Who Brings the Cookies?

1000ms 65535K

0 0

Description

Farmer John's N (1 <= N <= 1,000) cows conveniently numbered 1..N
decided to form M (1 <= M <= 100) study groups. A total of S_i (1
<= S_i <= 19) cows study in group G_i (namely cows G_i1, G_i2, ...).
A cow might study in more than one study group.

For each study group, one cow in the group must be chosen to bring cookies to the meeting. Cookies are costly and require time to acquire, so the cows want to divide the work of bringing cookies as fairly as possible.

They decided that if a cow attends meetings with size c_1, c_2, ..., c_K, she is only willing to bring cookies to at most ceil(1/c_1 + 1/c_2 + ... + 1/c_K) meetings.

Figure out which cow brings cookies to each meeting. If this isn't possible, just output "-1". Choose any solution if more than one is possible.

For each study group, one cow in the group must be chosen to bring cookies to the meeting. Cookies are costly and require time to acquire, so the cows want to divide the work of bringing cookies as fairly as possible.

They decided that if a cow attends meetings with size c_1, c_2, ..., c_K, she is only willing to bring cookies to at most ceil(1/c_1 + 1/c_2 + ... + 1/c_K) meetings.

Figure out which cow brings cookies to each meeting. If this isn't possible, just output "-1". Choose any solution if more than one is possible.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 contains many space-separated integers: S_i, G_i1, G_i2, ...

* Lines 2..M+1: Line i+1 contains many space-separated integers: S_i, G_i1, G_i2, ...

Output

* Lines 1..M: If a mapping is possible, line i contains the number of
the cow who brings cookies to study group i. Otherwise, line 1
contains just the integer -1.

Sample Input

5 6 3 2 4 5 2 1 3 3 1 2 3 1 1 2 2 5 3 2 3 4

Sample Output

5 1 3 1 2 4

Hint

Cow1 can bring cookies to at most 2 meetings, cow2 can bring 2, cow3 can
bring 2, cow4 can bring 1, and cow5 can bring 1.

Source

Editor