#include <iostream> #include <vector> using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) int N,M; vector<vector<int>> E; int main(){ cin >> N >> M; E.resize(N); rep(i,M){ int a,b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } vector<int> D(N,-1); vector<int> I; D[0] = 0; I.push_back(0); rep(i,I.size()){ int p = I[i]; for(int e : E[p]) if(D[e] == -1){ D[e] = D[p] + 1; I.push_back(e); } } cout << D[N-1] << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_inst;