P4929 [Template] Dancing Links (DLX).

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

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$.

The first line contains two integers $N, M$. The next $N$ lines each contain $M$ digits $0$ or $1$, representing the matrix.

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!`.

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