题目描述

农夫约翰的 $n$ 只奶牛（编号为 $1$ 到 $n$）决定成立 $m$ 个学习小组。在学习小组 $G_i$ 中有 $S_i$ 只牛，分别为牛 $G_{i,1},G_{i,2},\cdots,G_{i,S_i}$，一头牛可能会参加多个小组。对于每个学习小组，有一只牛必须在每次聚会的时候带饼干饮料请大家吃。因为买这些零食会消耗牛们那为数不多的零花钱，还会花费牛们宝贵的时间（这些金钱和时间本来是可以用来泡 的），所以牛们希望尽可能公平地分摊带零食的责任。牛们决定。如果一只牛参加了 $K$ 个学习小组，$K$ 个学习小组的大小分别为 $c_1,c_2,\cdots,c_K$，那么她最多负责为 $\lceil\frac1{c_1}+\frac1{c_2}+\cdots+\frac1{c_K}\rceil$ 个学习小组的聚会带零食。请计算出一个方案，决定每个学习小组的聚会由哪一头牛负责带零食。如果没有一种方案可行，输出「$-1$」。

输入格式

• 第一行：两个有空格分开的正整数 $n,m$；
• 接下来的 $m$ 行中，第 $i$ 行有若干由空格隔开的正整数 $S_i,G_{i,1},G_{i,2},\cdots,G_{1,S_i}$。

输出格式

• 如果有符合要求的方案，则有 $m$ 行，第 $i$ 行为第 $i$ 个学习小组带零食的奶牛编号；
• 如果没有符合要求的方案，则只有一个整数 $-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

数据规模与约定

对于 $100\%$ 的数据：$1\leq n\leq10^3$，$1\leq m\leq100$，$1\leq G_{i,j}\leq n$，$\forall i,j,k,G_{i,j}\not=G_{i,k}$。

题目来源

Usaco2009 Nov Gold