#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

template<class T = long long> constexpr T PINF(){ return std::numeric_limits<T>::max(); }
template<class T = long long> constexpr T MINF(){ return std::numeric_limits<T>::lowest(); }

class Query{
public:
    int a,t;
};

int bfs(vector<set<int>> &edges,int n){
    queue<Query> qs;
    int ret = PINF<int>();
    qs.push({0,0});
    vector<bool> is_searched(n,false);
    while(!qs.empty()){
        Query q = qs.front(); qs.pop();
        int a = q.a, t = q.t;
        if(a==(n-1)){ return t; }
        is_searched[a] = true;
        for(auto na : edges[a]){
            if(is_searched[na]==false){
                qs.push({na,t+1});
                is_searched[na]=true;
            }
        }
    }
    return PINF<int>();
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    int n,m;
    cin >> n >> m;
    int ui,vi;
    vector<set<int>> railways(n,set<int>());
    for(int i = 0; i < m; ++i){ //railwaysの辺
        cin >> ui >> vi;
        railways[ui-1].insert(vi-1);
        railways[vi-1].insert(ui-1);
    }

    vector<set<int>> roads(n,set<int>());
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i==j) continue;
            if(railways[i].count(j)==0){ //railwaysの辺がないところにroadsの辺がある
                roads[i].insert(j);
            }
        }
    }
    int ret = max(bfs(roads,n),bfs(railways,n));
    if(ret==PINF<int>()) cout << -1 << endl;
    else cout << ret << endl;
    return 0;
}