OI题库

【问题描述】

小明的N（1 <= N <= 1000）个朋友（编号为1到N）决定成立M个学习小组（1 <= M <= 100）。在学习小组G_i中有S_i个人，分别为G_i1、G_i2...一个人可能会参加多个小组。

对于每个学习小组，有一个人必须在每次聚会的时候带饼干饮料请大家吃。因为买这些零食会消耗我们那为数不多的零花钱，还会花费我们宝贵的时间，所以我们希望尽可能公平地分摊带零食的责任。

我们决定。如果一个人参加了K个学习小组，K个学习小组的大小分别为c_1、c_2、...、c_K，那么她最多负责为ceil(1/c_1 + 1/c_2 + ... + 1/c_K)个学习小组的聚会带零食。其中ceil为上取整函数。

请计算出一个方案，决定每个学习小组的聚会由哪一个人负责带零食。如果没有一种方案可行，输出"-1"。

输入格式：

＊第一行：两个由空格隔开的整数：N和M。

＊第二到第M+1行：第i+1行包含若干由空格隔开的整数：S_i，G_i1，G_i2...

样例输入（文件 cookie.in）：

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

解释：

第一、第二和第三个人愿意为两个学习小组的聚会带零食，第四和第五个人只愿意为一个学习小组带零食。

输出格式：

＊第1至第M行：如果有符合要求的方案，第i行有一个整数，表示为第i个学习小组的聚会带零食的人的编号。如果没有符合要求的方案，那么第一行只包含一个整数-1。

样例输出（文件 cookie.out）：

5
1
3
1
2
4