I think it's clear for the system of linear equations, that if M<N, than it's impossible. If M=N then it may be possible (and I know how to check). How about case M>N? We need to select N pairs that get an unambiguous solution?

You have to keep only the lineary independet ones, I think.
What I did is I kept only the first 5 ones, which contain certain number (so the matrix in the end was at most 5000 rows long, containing at least 5 rows, containing a digit at each position) and it passed system test (otherwise the solution was right, but too slow)

Just find at least one odd loop in each connected component

hmm i make this but i get TLE( test 12)... (with a BFS) any ideea why?

Strange. It will not work for this test (A_i can be arbitrary).

43 43
2 3 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
2 8 0
2 9 0
2 10 0
2 11 0
2 12 0
2 13 0
3 14 0
3 15 0
3 16 0
3 17 0
3 18 0
3 19 0
4 20 0
4 21 0
4 22 0
4 23 0
4 24 0
4 25 0
5 26 0
5 27 0
5 28 0
5 29 0
5 30 0
5 31 0
6 32 0
6 33 0
6 34 0
6 35 0
6 36 0
6 37 0
7 38 0
7 39 0
7 40 0
7 41 0
7 42 0
7 43 0

Edited by author 20.01.2018 04:30