1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <cmath>
5. #include <set>
6. #include <unordered_set>
7. #include <random>
8. #include <ctime>
9. #include <queue>
10. #include <utility>
11.  
12. int nn, mm;
13. int MAXN = 1e6 * 2;
14.  
15.  
16. int IndexToNumber(int ii, int jj) {
17.     return ii * mm + jj;
18. }
19.  
20. int BitByIndex(int table, int ii, int jj) {
21.     return (table >> IndexToNumber(ii, jj)) % 2;
22. }
23.  
24. bool Check(int table) {
25.     for (int ii = 0; ii < nn; ++ii) {
26.         for (int jj = 0; jj < mm; ++jj) {
27.             if (ii > 0) {
28.                 if (BitByIndex(table, ii, jj) == BitByIndex(table, ii - 1, jj)) {
29.                     return false;
30.                 }
31.             }
32.             if (jj > 0) {
33.                 if (BitByIndex(table, ii, jj) == BitByIndex(table, ii, jj - 1)) {
34.                     return false;
35.                 }
36.             }
37.         }
38.     }
39.     return true;
40. }
41.  
42.  
43. int XorByIndex(int table, int ii, int jj) {
44.     return table xor (1 << IndexToNumber(ii, jj));
45. }
46.  
47. void PushNew(std::vector<bool> &used, std::queue<std::pair<int, int>> &qu, int table, int num) {
48.     for (int ii = 0; ii < nn; ++ii) {
49.         for (int jj = 0; jj < mm; ++jj) {
50.             if (ii + 1 != nn) {
51.                 int new_table = XorByIndex(table, ii, jj);
52.                 new_table = XorByIndex(new_table, ii + 1, jj);
53.  
54.                 if (!used[new_table]) {
55.                     used[new_table] = true;
56.                     qu.push({new_table, num + 1});
57.                 }
58.             }
59.  
60.             if (jj + 1 != mm) {
61.                 int new_table = XorByIndex(table, ii, jj);
62.                 new_table = XorByIndex(new_table, ii, jj + 1);
63.  
64.                 if (!used[new_table]) {
65.                     used[new_table] = true;
66.                     qu.push({new_table, num + 1});
67.                 }
68.             }
69.         }
70.     }
71. }
72.  
73. int Bfs(int table) {
74.     std::vector<bool> used(MAXN);
75.     std::queue<std::pair<int, int>> qu;
76.     qu.push({table, 0});
77.     used[table] = true;
78.     while (!qu.empty()) {
79.         auto item = qu.front();
80.         if (Check(item.first)) {
81.             return item.second;
82.         }
83.         qu.pop();
84.         PushNew(used, qu, item.first, item.second);
85.     }
86.     return -1;
87. }
88.  
89. int main() {
90.     std::cin >> nn >> mm;
91.     int table = 0;
92.     for (int i = 0; i < nn; ++i) {
93.         for (int j = 0; j < mm; ++j) {
94.             char sim;
95.             std::cin >> sim;
96.             if (sim == '1') {
97.                 table = table | (1 << (i * mm + j));
98.             }
99.         }
100.     }
101.     std::cout << Bfs(table);
102. }
103.