Cerința

Se consideră un panou de dimensiuni \(n \times m\) pe care sunt așezate \(nm\) becuri. Becul de pe rândul \(i\) și coloana \(j\) se notează \((i,j)\). Inițial, fiecare bec este stins (\(0\)) sau aprins (\(1\)). Putem efectua următoarele comenzi de oricâte ori:

• Se alege un rând \(i\) (\(1 \le i \le n\)) și se inversează starea tuturor becurilor de pe rândul \(i\) (\(0\rightarrow 1,1\rightarrow 0\));
• Se alege o coloană \(j\) (\(1 \le j \le m\)) și se inversează starea tuturor becurilor de pe coloana \(j\) (\(0\rightarrow 1,1\rightarrow 0\)).

Găsiți o secvență cu un număr minim de comenzi care conduce la aprinderea tuturor becurilor.

Date de intrare

Pe prima linie se află numerele \(n\) și \(m\). Pe a \(i\)-a dintre următoarele \(n\) linii se găsește o secvență de \(m\) numere care sunt fie \(0\), fie \(1\). Al \(j\)-lea număr reprezintă starea becului \((i,j)\).

Date de ieșire

Programul va afișa DA, dacă este posibilă aprinderea tuturor becurilor și NU în caz contrar. Dacă răspunsul este DA, pe a doua linie se vor afișa indicii liniilor inversate. Apoi, pe a treia linie se vor afișa indicii coloanelor inversate. Atât pe a doua, cât și pe a treia linie, numerele vor fi afișate în ordine crescătoare.

Restricții și precizări

• \(2 \le n,m \le 500\)
• Se garantează că pentru testele date, există o unică soluție optimă
• Pentru 10 de puncte, se garantează că soluția optimă inversează doar rânduri
• Pentru alte 10 de puncte, se garantează că soluția optimă inversează un rând și o coloană

Exemplu 1:

Intrare

2 5
1 0 1 1 0
0 1 0 0 1

Ieșire

DA
2
2 5

Explicație

Se inversează rândul \(2\) și coloanele \(2\) și \(5\).

Exemplu 2:

Intrare

2 5
1 0 1 1 1
0 1 0 0 1

Ieșire

NU

Explicație

Se poate demonstra că nu există soluție pentru acest test.