Background

This problem is a Dancing Links template for the Exact Cover problem.

Problem Description

Given a matrix with $N$ rows and $M$ columns, each element in the matrix is either $1$ or $0$.

You need to select some rows from the matrix so that for every column $j$ of the matrix, among the selected rows, there is one and only one row whose $j$-th element is $1$.

Input Format

The first line contains two integers $N, M$.

The next $N$ lines each contain $M$ digits $0$ or $1$, representing the matrix.

Output Format

Output one line containing several integers representing the answer. Separate numbers with spaces. Any feasible solution is acceptable, and the order can be arbitrary.

If there is no solution, output No Solution!.

3 3
0 0 1
1 0 0
0 1 0

2 1 3

3 3
1 0 1
1 1 0
0 1 1

No Solution!

Hint

For $100\%$ of the testdata, $N, M \leq 500$, and the number of $1$ in the matrix is guaranteed to be at most $5000$.

Translated by ChatGPT 5