题目描述

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.

农夫约翰的N（1 <= N <= 1000）只奶牛（编号为1到N）决定成立M个学习小组（1 <= M <= 100）。在学习小组G_i中有S_i只牛，分别为牛G_i1、G_i2⋯⋯一头牛可能会参加多个小组。 对于每个学习小组，有一只牛必须在每次聚会的时候带饼乾饮料请大家吃（衰～）。因为买这些零食会消耗牛们那为数不多的零花钱，还会花费牛们宝贵的时间（这些金钱和时间本来是可以用来泡MM的），所以牛们希望尽可能公平地分摊带零食的责任。 牛们决定。如果一只牛参加了K个学习小组，K个学习小组的大小分别为c_1、c_2、⋯、c_K，那麽她最多负责为ceil(1/c_1 + 1/c_2 + ⋯ + 1/c_K)个学习小组的聚会带零食。其中ceil为上取整函数。 请计算出一个方案，决定每个学习小组的聚会由哪一头牛负责带零食。如果没有一种方案可行，输出"-1"。

输入格式

* 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 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.

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

5 
1 
3 
1 
2 
4 

提示

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.