/*               ∧∧∩               ( ゚∀゚)/ キタ━━━━━━(゚∀゚)━━━━━━!!!!             ⊂   ノ  ゆっくり見てってね!!!!!!!!              (つ ノ     o          (ノ      \      ☆              |      o           (⌒ ⌒ヽ   /     ☆     \  (´⌒  ⌒  ⌒ヾ   /       ('⌒ ; ⌒   ::⌒  )      (´     )     ::: ) /   ☆─ (´⌒;:    ::⌒`) :;  ) */ #include #include using namespace std; using namespace atcoder; #define elif else if #define rep(i, s, n) for (int i=s; i>i)&1) typedef long long ll; typedef long double ld; ld pi = 3.14159265358979; inline void scan(){} template inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);} // print(a, b, c) => cout << a << ' ' << b << ' ' << c << endl; inline void print(){} template inline void print(Head&head,Tail&... tail){std::cout< std::istream &operator>>(std::istream&is,std::vector&v){for(T &in:v){is>>in;}return is;} template std::ostream &operator<<(std::ostream&os,const std::vector&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;} // 2地点の距離(long double) long double coor_dist(long double xi, long double yi, long double xj, long double yj) { return sqrt(abs((xi - xj) * (xi - xj)) + abs((yi - yj) * (yi - yj))); } // 回文かどうかの判定 bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;} template void chmax(T& a, T b) { if (a < b) a = b; } template void chmin(T& a, T b) { if (a > b) a = b; } #define mod 998244353 using mint = modint998244353; int op(int a, int b) {return max(a, b);} int e() {return 0;} int mapping(int f, int x) {return (f == 1e9 ? x : f);} int composition(int f, int g) {return (f == 1e9 ? g : f);} int id() {return 1e9;} signed main() { cin.tie(nullptr); cout << fixed << setprecision(10); ios::sync_with_stdio(false); int n, m; cin >> n >> m; vector> side(n); rep(i, 0, m) { int u, v; cin >> u >> v; u--; v--; side[u].push_back(v); } auto f = [&](auto&& f, int s, int g) -> int { vector dist(n, -1); queue q; dist[s] = 0; q.push(s); while(!q.empty()) { int pos = q.front(); q.pop(); for(int to : side[pos]) { if(dist[to] != -1) continue; dist[to] = dist[pos]+1; q.push(to); } } return dist[g]; }; int f_0_a, f_0_b, f_a_b, f_b_a, f_a_0, f_b_0; f_0_a = f(f, 0, n-2); f_0_b = f(f, 0, n-1); f_a_b = f(f, n-2, n-1); f_b_a = f(f, n-1, n-2); f_a_0 = f(f, n-2, 0); f_b_0 = f(f, n-1, 0); int ans = 1e9; if(f_0_a != -1 && f_a_b != -1 && f_b_0 != -1) ans = f_0_a+f_a_b+f_b_0; if(f_0_b != -1 && f_b_a != -1 && f_a_0 != -1) chmin(ans, f_0_b+f_b_a+f_a_0); if(ans == 1e9) ans = -1; cout << ans << endl; }