#include using namespace std; #define int long long #define fi first #define se second #define PB push_back #define pii pair #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define __Suchi__ signed main() #define TIME (1.0 * clock()/CLOCKS_PER_SEC) const int N = 1e5+7; const int M = 1e3+1; int n, m, k; int d[N][4]; int vis[N]; vector g[N]; void bfs(int s, int idx){ memset(vis, 0 , sizeof vis); queue q; q.push(s); d[s][idx] = 0; while(!q.empty()){ int u = q.front(); q.pop(); if (vis[u]) continue; vis[u] = 1; for(auto v : g[u]) if (d[v][idx] > d[u][idx] + 1){ d[v][idx] = d[u][idx] + 1; q.push(v); } } } void solve(){ FOR(i,1,k){ int x,y ; cin >> x >> y; g[x].PB(y); } FOR(i,1,n) d[i][1] = d[i][2] = d[i][3] = 1000000000; bfs(1, 1); bfs(n-1, 2); bfs(n, 3); // FOR(i,1,n) cout << d[i][1] << " "; // cout << "\n"; // FOR(i,1,n) cout << d[i][2] << " "; // cout << "\n"; // FOR(i,1,n) cout << d[i][3] << " "; // cout << "\n"; // 1 -> n -> n-1 -> 1 // 1 -> n-1 -> n -> 1 int res = min(d[n-1][1] + d[n][2] + d[1][3], d[n][1] + d[n-1][3] + d[1][2]); cout << (res >= 1000000000 ? -1 : res); } __Suchi__{ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; FOR(i, 1, t){ cin >> n >> k; solve(); } cerr << "Time elapsed: " << TIME << "s.\n"; return (0 ^ 0); }