Conectate

Time limit: 0.5s Memory limit: 64MB Input: Output:

Cerință

O matrice binară se numește conectată dacă se poate ajunge din orice valoare de 11 în orice altă valoare de 11 trecând doar prin valori de 11. O matrice care conține doar 00 se consideră conectată.

Se dă o matrice binară CC (nu neapărat conectată). Să se găsească două matrici binare conectate AA și BB astfel încât să se respecte următoarea condiție: Cij=1C_{ij}=1 dacă și numai dacă AijBijA_{ij} \neq B_{ij}.

Se garantează că matricea CC conține cel puțin un 00 pe fiecare rând.

Date de intrare

Pe prima linie se vor afla valorile nn, mm (dimensiunile matricei). Următoarele nn linii conțin fiecare câte mm valori din mulțimea {0,1}\{0,1\}, reprezentând elementele matricei CC.

Date de ieșire

Dacă nu există soluție, se va afișa 1-1. Altfel, se va afișa matricea AA sub forma a nn linii conținând câte mm valori din mulțimea {0,1}\{0,1\}, apoi se va afișa matricea BB în același mod. Între cele două matrici se poate afișa un rând liber, chiar dacă nu este necesar.

Restricții și precizări

Pentru toate testele, se respectă 1n,m10001 \le n, m \le 1000.

# Punctaj Restricții
1 4 Valorile de 11 din CC sunt conectate și 2n1002 \le n\le 100.
2 7 Valorile de 00 din CC sunt conectate și 2n1002 \le n\le 100.
3 17 n=1n=1
4 21 n2n\ge 2, iar matricea CC este o tablă de șah (Cij=1C_{ij}=1 dacă și numai dacă ii și jj au parități diferite).
5 51 n2n\ge 2

Exemplul 1

stdin

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

stdout

0 1 1 1
0 1 0 0
0 1 1 1
1 1 1 0

0 0 1 0
0 1 1 0
0 0 1 0
0 0 0 0

Explicație

Exemplul este ilustrat în imaginea de mai sus. În stânga-sus este reprezentată matricea CC (celulele marcate cu 'X' conțin 11). Jos sunt reprezentate cele două matrici AA și BB (celulele colorate conțin 11). În dreapta-sus este reprezentată suprapunerea celor două matrici AA și BB. Se poate observa cum celulele marcate cu 'X' apar în exact una din matricile AA și BB, conform cerinței.

Acasta nu este unica soluție.

Exemplul 2

stdin

1 9
0 1 1 0 0 1 1 1 0

stdout

0 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0

Explicație

Rândul liber dintre cele două matrici este opțional.

Exemplul 3

stdin

1 9
0 1 1 0 1 0 1 1 0

stdout

-1

Explicație

În acest caz, nu există soluție.

Log in or sign up to be able to send submissions!