#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#ifdef DEBUG
    #define var(x) cerr << #x << ": " << x << '\n';
    #define range(a, b) cerr << #a <<", " << #b << ": "; for (auto _it = a; _it != b; ++_it) cerr << *_it << ' '; cerr <<'\n';
#else
    #define cerr if (false) cerr
    #define var(x)
    #define range(a, b)
#endif

#define pii pair<int, int>
#define F first
#define S second
#define T(x, i) get<i>(x)
#define all(v) v.begin(), v.end()
#define forn(i, n) for (int i = 0; i < n; i++)

const int MAXN = 5e5 + 10;
int n, m;


vector<int> g[MAXN];
int dsu[MAXN];
int sz[MAXN];

int get(int x) {
    if (dsu[x] == x) return x;
    return dsu[x] = get(dsu[x]);
}

void unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    dsu[a] = b;
    sz[b] += sz[a];
}

vector<int> bfs(int st) {
    queue<int> q;
    q.push(st);
    vector<int> d(n, MAXN);
    d[st] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto to : g[v]) {
            if (d[to] == MAXN) {
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }
    return d;
}

void solve() {
    forn(i, n) {
        g[i].clear();
        dsu[i] = i;
        sz[i] = 1;
    }
    vector<pii> e;
    forn(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e.push_back({a, b});
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist_start = bfs(0);
    vector<int> dist = bfs(n-1);
    int ans = -1;

    vector<int> dp(n, MAXN * 10);
    vector<int> cost(n, MAXN * 10);
    vector<int> idx(n);
    iota(all(idx), 0);
    sort(all(idx), [&](int a, int b) {
        return dist[a] > dist[b];
    });
    for (auto v : idx) {
        int cnt_prev = 0;
        int cnt_next = 0;
        int cnt_same = 0;
        for (auto to : g[v]) {
            if (dist[to] == dist[v] + 1) {
                cnt_next++;
            }
            if (dist[to] == dist[v]) {
                cnt_same++;
            }
            if (dist[to] == dist[v] - 1) {
                cnt_prev++;
            }
        }
        if (cnt_prev > 1) {
            dp[v] = 0;
        } else if (cnt_same > 0) {
            dp[v] = 1;
        } else {
            for (auto to : g[v]) {
                if (dist[to] == dist[v] + 1) {
                    dp[v] = min(dp[v], dp[to] + 2);
                }
            }
        }
    }
    forn(i, n) {
        cost[i] = dist_start[i] + dp[i] + dist[i]; 
    }
    cost[n-1] = 0;
    range(dist_start.begin(), dist_start.end());
    range(dist.begin(), dist.end());
    range(dp.begin(), dp.end());
    range(cost.begin(), cost.end());
    sort(all(e), [&](pii a, pii b) {
        return max(cost[a.F], cost[a.S]) < max(cost[b.F], cost[b.S]);
    });
    for (auto [a, b] : e) {
        unite(a, b);
        if (get(0) == get(n-1)) {
            if (max(cost[a], cost[b]) > 2 * MAXN) {
                cout << "-1\n";
            } else cout << max(cost[a], cost[b]) << '\n';
            return;
        }
    }
}

signed main() {
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> m) solve();
}