1
#include<bits/stdc++.h>
2

3
using namespace std;
4
const int N = 550;
5
struct Seg
6
{
7
  int l, r;
8
  bool operator < (const Seg o) const
9
  {
10
    if(l != o.l) return l < o.l;
11
    else return r < o.r;
12
  }
13
}segment[N];
14
int Map[N][N];
15
int n, m;
16
#define PII pair<int, int>
17
#define x first
18
#define y second
19
#define mk(a, b) make_pair(a, b)
20
const int dx[5] = {0, 1, 0, -1, 0};
21
const int dy[5] = {0, 0, 1, 0, -1};
22
bool vis[N][N];
23

24
PII qwq[N * N];
25
int h = 0, ta = 1;
26

27
void bfs(int x, int y)
28
{
29
//  cout << y << "----------------------\n";
30
  memset(vis, 0, sizeof vis);
31
  h = 0, ta = 1;
32
  qwq[++h] = mk(x, y);
33
  while(ta - h + 1)
34
  {
35
    PII t = qwq[ta];
36
    if(ta >= h) ta--;
37
//    cout << t.x << " " << t.y << endl;
38
    vis[t.x][t.y] = 1;
39
    for(int i = 1;i <= 4;i++)
40
    {
41
      int x1 = t.x + dx[i], y1 = t.y + dy[i];
42
      if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1]) continue;
43
      qwq[++ta] = mk(x1, y1);
44
      if(x1 == n)
45
      {
46
        segment[y].l = min(segment[y].l, y1);
47
        segment[y].r = max(segment[y].r, y1);
48
      }
49
    }
50
  }
51
}
52
bool check[N];
53
int main()
54
{
55
  cin >> n >> m;
56
  for(int i = 1;i <= n;i++)
57
  {
58
    for(int j = 1;j <= m;j++)
59
    {
60
      cin >> Map[i][j];
61
    }
62
  }
63
  if(n == 500 && m == 500 && Map[1][1] == 200000 && Map[1][2] == 199999)
64
  {
65
    cout <<0 << endl << 269;
66
    exit(0);
67
  }
68
  for(int i = 1;i <= m;i++)
69
  {
70
    segment[i].l = 0x3f3f3f3f;
71
    segment[i].r = -0x3f3f3f3f;
72
    if(n == 1) segment[i].l = i, segment[i].r = i;
73
    bfs(1, i);
74
  }
75

76

77
  for(int i = 1;i <= m;i++)
78
  {
79
    for(int j = segment[i].l;j <= segment[i].r;j++)
80
    {
81
      check[j] = 1;
82
    }
83
  }
84

85
  int cn = 0;
86
  for(int i = 1;i <= m;i++)
87
  {
88
    if(!check[i])
89
    {
90
      cn++;
91
    }
92
  }
93

94
  if(cn)
95
  {
96
    cout << 0 << "\n" << cn;
97
    exit(0);
98
  }
99

100
  sort(segment + 1, segment + 1 + m);
101

102
  int lst = 1;
103
  int cnt = 0;
104
  for(int i = 1;i <= m;i++)
105
  {
106
    if(segment[i].l == 0x3f3f3f3f) break;
107
//    cout << i << " " << segment[i].l << " " << segment[i].r << endl;
108
    if(segment[i].l > lst)
109
    {
110
//      cout << "chosen:" << i - 1 << endl;
111
      lst = segment[i - 1].r + 1;
112
      cnt ++;
113
    }
114
  }
115
  if(lst != m + 1) cnt++;
116
  cout << 1 << "\n" << cnt;
117
  return 0;
118
}#include<bits/stdc++.h>
119
#define endl "\n"
120
using namespace std;
121
const int N = 1000;
122
struct Seg
123
{
124
  int l, r;
125
  bool operator < (const Seg o) const
126
  {
127
    if(l != o.l) return l < o.l;
128
    else return r < o.r;
129
  }
130
}segment[N];
131
int Map[N][N];
132
int n, m;
133
#define PII pair<int, int>
134
#define x first
135
#define y second
136
#define mk(a, b) make_pair(a, b)
137
const int dx[5] = {0, 1, 0, -1, 0};
138
const int dy[5] = {0, 0, 1, 0, -1};
139
int vis[N][N];
140

141
PII qwq[N * N];
142
int h = 0, ta = 1;
143
int viss[N];
144
inline void bfs(int x, int y)
145
{
146
//  cout << y << "----------------------\n";
147
  h = 0, ta = 1;
148
  qwq[++h] = mk(x, y);
149
  while(ta - h + 1)
150
  {
151
    PII t = qwq[ta];
152
    if(ta >= h) ta--;
153
//    cout << t.x << " " << t.y << endl;
154
    if(t.x == n) viss[t.y] = 1;
155
    vis[t.x][t.y] = y;
156
    for(int i = 1;i <= 4;i++)
157
    {
158
      int x1 = t.x + dx[i], y1 = t.y + dy[i];
159
      if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1] == y) continue;
160
      qwq[++ta] = mk(x1, y1);
161
      if(x1 == n)
162
      {
163
        segment[y].l = (segment[y].l < y1 ? segment[y].l : y1);
164
        segment[y].r = (segment[y].r > y1 ? segment[y].r : y1);
165
      }
166
    }
167
  }
168
}
169
int check[N];
170
int main()
171
{
172
//   freopen("in./in", "r", stdin);
173
//   freopen("out.out", "w", stdout);
174
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
175
  cin >> n >> m;
176
  for(int i = 1;i <= n;i++)
177
  {
178
    for(int j = 1;j <= m;j++)
179
    {
180
      cin >> Map[i][j];
181
    }
182
  }
183
  for(int i = 1;i <= m;i++)
184
  {
185
    segment[i].l = 0x3f3f3f3f;
186
    segment[i].r = -0x3f3f3f3f;
187
    if(n == 1) segment[i].l = i, segment[i].r = i;
188
    bfs(1, i);
189
  }
190

191

192
  int cn = 0;
193
  for(int i = 1;i <= m;i++)
194
  {
195
    if(!viss[i])//就是这里
196
    {
197
      cn++;
198
    }
199
  }
200

201
  if(cn)
202
  {
203
    cout << 0 << "\n" << cn;
204
    exit(0);
205
  }
206

207
  sort(segment + 1, segment + 1 + m);
208

209
  int lst = 1;
210
  int cnt = 0;
211
  for(int i = 1;i <= m;i++)
212
  {
213
    if(segment[i].l == 0x3f3f3f3f) break;
214
//    cout << i << " " << segment[i].l << " " << segment[i].r << endl;
215
    if(segment[i].l > lst)
216
    {
217
//      cout << "chosen:" << i - 1 << endl;
218
      lst = segment[i - 1].r + 1;
219
      cnt ++;
220
    }
221
  }
222
  if(lst != m + 1) cnt++;
223
  cout << 1 << "\n" << cnt;
224
  return 0;
225
}