【模板】舞蹈链(DLX)

题目背景

本题是舞蹈链模板——精确覆盖问题

题目描述

给定一个$N$行$M$列的矩阵,矩阵中每个元素要么是1,要么是0 你需要在矩阵中挑选出若干行,使得对于矩阵的每一列$j$,在你挑选的这些行中,有且仅有一行的第$j$个元素为$1$

输入输出格式

输入格式


第一行两个数$N,M$ 接下来$N$行,每行$M$个数字0或1,表示这个矩阵

输出格式


一行输出若干个数表示答案,两个数之间用空格隔开,输出任一可行方案均可,顺序随意 若无解,输出“No Solution!”(不包含引号)

输入输出样例

输入样例 #1

3 3
0 0 1
1 0 0
0 1 0

输出样例 #1

2 1 3

输入样例 #2

3 3
1 0 1
1 1 0
0 1 1

输出样例 #2

No Solution!

说明

$N,M\leq 500$ 保证矩阵中1的数量不超过$5000$个