2713

2713. 重复覆盖问题

题目

给定一个 $N \times M$ 的数字矩阵 $A$，矩阵中的元素 $A_{i,j} \in \{0,1\}$。

请你在矩阵中找到一个行的集合，使得这些行中，每一列都包含数字 $1$，并且集合中包含的行数尽可能少。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含 $M$ 个整数（$0$ 或 $1$），表示完整的数字矩阵。

输出格式

输出共两行。

第一行输出集合最少需要包含的行数。

第二行输出集合中包含的行的编号（行编号 $1 \sim N$）。

如果方案不唯一，则以任意顺序输出任意方案即可。

数据范围

$1 \le N,M \le 100$,

数据保证有解且答案不超过 $20$。

输入样例：

4 4
1 0 1 0
1 1 0 1
0 1 0 0
0 0 0 1

输出样例：

2
1 2

题解