#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, h[1111][1111];
int a[1111][1111], b[1111][1111];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[1111][1111];
pair<int, int> c[1111];
void dfs(int x, int y)
{
    if (vis[x][y]) {
        return;
    }
    vis[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && h[dx][dy] < h[x][y]) {
            if (!vis[dx][dy]) {
                dfs(dx, dy);
            }
            a[x][y] = min(a[dx][dy], a[x][y]);
            b[x][y] = max(b[dx][dy], b[x][y]);
        }
    }
}
signed main()
{
    freopen("flow.in", "r", stdin);
    freopen("flow.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> h[i][j];
        }
    }
    memset(a, 0x3f3f3f3f, sizeof(a));
    memset(b, -1, sizeof(b));
    for (int i = 1; i <= m; ++i) {
        a[n][i] = i;
        b[n][i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        if (!vis[1][i]) {
            dfs(1, i);
        }
    }
    for (int i = 1; i <= m; ++i) {
        c[i].first = a[1][i];
        c[i].second = b[1][i];
    }
    int r = m, ans = 0, l = 1;
    sort(c + 1, c + m + 1);
    bool ok = 1;
    for (int i = 1, j = 1; i <= m; ++i) {
        int tp = LLONG_MIN;
        while (j <= m && c[j].first <= l) {
            tp = max(c[j].second, tp);
            ++j;
        }
        if (tp >= r) {
            cout << 1 << '\n';
            cout << ans + 1 << '\n';
            return 0;
        }
        if (tp < l) {
            ans = -1;
            break;
        }
        l = tp + 1;
        ans++;
        i = j - 1;
    }
    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
        cnt += vis[n][i];
    }
    cout << 0 << '\n';
    cout << m - cnt << '\n';
    return 0;
}