#include<bits/stdc++.h>
using namespace std;
vector<int> r[405], rl[405];
int n, m, u, v, rd[405], rld[405];
void dfs(vector<int> a[], int d[], int node, int dist) {
d[node] = dist;
for(auto i: a[node]) {
if(d[i] == -1 || d[i] > dist + 1) {
dfs(a, d, i, dist + 1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
r[i].push_back(j);
r[j].push_back(i);
}
rd[i] = rld[i] = -1;
}
for(int i=0; i<m; i++) {
cin >> u >> v;
r[u].erase(remove(r[u].begin(), r[u].end(), v), r[u].end());
r[v].erase(remove(r[v].begin(), r[v].end(), u), r[v].end());
rl[u].push_back(v);
rl[v].push_back(u);
}
dfs(r, rd, 1, 0);
dfs(rl, rld, 1, 0);
if(rd[n] == -1 || rld[n] == -1) {
cout << -1;
} else {
cout << max(rd[n], rld[n]);
}
return 0;
}