#include <iostream>
#include <vector>
#include <queue>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using P = pair<int, int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

constexpr int diry[] = {0, 1, 0, -1};  // >,v,<,^
constexpr int dirx[] = {1, 0, -1, 0};  // >,v,<,^
constexpr int sx = 0;
constexpr int sy = 0;
constexpr int INF = 1 << 30;

int main()
{
    while (true) {
        int h, w;
        cin >> h >> w;
        if (h == 0 and w == 0) {
            break;
        }


        const int gy = h - 1;
        const int gx = w - 1;
        vector<vector<bool>> yoko(h, vector<bool>(w - 1, false));  // (i,j)->(i,j+1)
        vector<vector<bool>> tate(h - 1, vector<bool>(w, false));  // (i,j)->(i+1,j)
        for (int i = 0; i < 2 * h - 1; i++) {
            for (int j = 0; j < ((i % 2 == 0) ? w - 1 : w); j++) {
                int c;
                cin >> c;
                ((i % 2 == 0) ? yoko : tate)[i / 2][j] = (c == 1);
            }
        }
        auto ok = [&](const int y, const int x, const int dir) -> bool {  // >,v,<,^
            if (dir == 0) {
                if (x == w - 1) {
                    return false;
                } else {
                    return not yoko[y][x];
                }
            } else if (dir == 1) {
                if (y == h - 1) {
                    return false;
                } else {
                    return not tate[y][x];
                }

            } else if (dir == 2) {
                if (x == 0) {
                    return false;
                } else {
                    return not yoko[y][x - 1];
                }

            } else {
                if (y == 0) {
                    return false;
                } else {
                    return not tate[y - 1][x];
                }
            }
        };
        vector<vector<int>> distance(h, vector<int>(w, INF));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int maxi = 0;
                for (int k = 0; k < 4; k++) {  // >,v,<,^
                    if (k == 0) {
                        if (j == w - 1 or yoko[i][j]) {
                            continue;
                        }
                        yoko[i][j] = true;
                    } else if (k == 1) {
                        if (i == h - 1 or tate[i][j]) {
                            continue;
                        }
                        tate[i][j] = true;
                    } else if (k == 2) {
                        if (j == 0 or yoko[i][j - 1]) {
                            continue;
                        }
                        yoko[i][j - 1] = true;
                    } else if (k == 3) {
                        if (i == 0 or tate[i - 1][j]) {
                            continue;
                        }
                        tate[i - 1][j] = true;
                    }
                    vector<vector<bool>> used(h, vector<bool>(w, false));
                    queue<pair<P, int>> q;
                    q.push(make_pair(make_pair(i, j), 0));
                    used[i][j] = true;
                    int ans = INF;
                    while (not q.empty()) {
                        const P pos = q.front().first;
                        const int y = pos.first;
                        const int x = pos.second;
                        const int dist = q.front().second;
                        if (y == gy and x == gx) {
                            ans = dist;
                            break;
                        }
                        q.pop();
                        for (int d = 0; d < 4; d++) {
                            if (ok(y, x, d)) {
                                const int newy = y + diry[d];
                                const int newx = x + dirx[d];
                                if (not used[newy][newx]) {
                                    used[newy][newx] = true;
                                    q.push(make_pair(make_pair(newy, newx), dist + 1));
                                }
                            }
                        }
                    }
                    maxi = max(maxi, ans);

                    if (k == 0) {
                        yoko[i][j] = false;
                    } else if (k == 1) {
                        tate[i][j] = false;
                    } else if (k == 2) {
                        yoko[i][j - 1] = false;
                    } else if (k == 3) {
                        tate[i - 1][j] = false;
                    }
                }
                distance[i][j] = maxi;
            }
        }
        // show(distance);

        int inf = 0;
        int sup = INF;
        while (inf < sup) {
            const int mid = (inf + sup) / 2;
            bool goal = false;
            vector<vector<bool>> used(h, vector<bool>(w, false));
            queue<pair<P, int>> q;
            q.push(make_pair(make_pair(sy, sx), 0));
            used[sy][sx] = true;
            while (not q.empty()) {
                const P pos = q.front().first;
                const int y = pos.first;
                const int x = pos.second;
                if (y == gy and x == gx) {
                    goal = true;
                    break;
                }
                const int dist = q.front().second;
                q.pop();
                for (int d = 0; d < 4; d++) {
                    if (ok(y, x, d)) {
                        const int newy = y + diry[d];
                        const int newx = x + dirx[d];
                        if (not used[newy][newx] and distance[newy][newx] + dist + 1 <= mid) {
                            used[newy][newx] = true;
                            q.push(make_pair(make_pair(newy, newx), dist + 1));
                        }
                    }
                }
            }
            if (goal) {
                sup = mid;
            } else {
                if (inf == mid) {
                    break;
                }
                inf = mid;
            }
        }
        if (sup == INF) {
            cout << -1 << endl;
        } else {
            cout << sup << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3128