#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
long long max(long long a, int b){return std::max(a, (long long)b);}
long long max(int a, long long b){return std::max((long long)a, b);}
long long min(long long a, int b){return std::min(a, (long long)b);}
long long min(int a, long long b){return std::min((long long)a, b);}
long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}





/*
template<typename edge_weight>
struct edge_base{
  using weight = edge_weight;
  int to();
  int from();
  int id();
  weight wei();
  static weight z();
  edge_base<weight> reverse();
};
*/

template<typename edge_weight>
struct simple_edge{
  using weight = edge_weight;
  int s, t;
  simple_edge(): s(-1), t(-1){}
  simple_edge(int a, int b): s(a), t(b){}
  int to(){return t;}
  int from(){return s;}
  int id(){return -1;}
  weight wei(){return 1;}
  static weight z(){return 0;}
  simple_edge<weight> reverse(){return simple_edge<weight>{t, s};}
};

template<typename edge_weight>
struct weighted_edge{
  using weight = edge_weight;
  int s, t;
  weight w;
  weighted_edge(): s(-1), t(-1), w(0){}
  weighted_edge(int a, int b, weight c): s(a), t(b), w(c){}
  int to(){return t;}
  int from(){return s;}
  int id(){return -1;}
  weight wei(){return w;}
  static weight z(){return 0;}
  weighted_edge<weight> reverse(){return weighted_edge<weight>{t, s, w};}
};

template<typename edge_weight>
struct labeled_edge{
  using weight = edge_weight;
  int s, t, i;
  labeled_edge(): s(-1), t(-1), i(-1){}
  labeled_edge(int a, int b, int i): s(a), t(b), i(i){}
  int to(){return t;}
  int from(){return s;}
  int id(){return i;}
  weight wei(){return 1;}
  static weight z(){return 0;}
  labeled_edge<weight> reverse(){return labeled_edge<weight>{t, s, i};}
};

template<typename edge_weight>
struct weighted_labeled_edge{
  using weight = edge_weight;
  int s, t;
  weight w;
  int i;
  weighted_labeled_edge(): s(-1), t(-1), w(0), i(-1){}
  weighted_labeled_edge(int a, int b, weight w, int i): s(a), t(b), w(w), i(i){}
  int to(){return t;}
  int from(){return s;}
  int id(){return i;}
  weight wei(){return w;}
  static weight z(){return 0;}
  weighted_labeled_edge<weight> reverse(){return weighted_labeled_edge<weight>{t, s, w, i};}
};



#include <limits>

namespace graph_algorithm{
  template<typename T>
  using vec = std::vector<T>;
  // O(V + E)
  // 辺の重みが1
  template<typename edge>
  struct bfs_shortest_path{
  private:
    using weight = typename edge::weight;
    using dist_p = std::pair<weight, int>;
    vec<vec<edge>> &g;
  public:
    bfs_shortest_path(vec<vec<edge>> &g): g(g){}
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
    vec<weight> dist;
    vec<edge> par;
    void build(int s){
      int n = g.size();
      if(dist.empty()){
        dist.resize(n, inf);
        par.resize(n, edge{});
      }else{
        std::fill(dist.begin(), dist.end(), inf);
        std::fill(par.begin(), par.end(), edge{});
      }
      std::queue<dist_p> que;
      dist[s] = edge::z();
      que.push(dist_p(edge::z(), s));
      while(!que.empty()){
        auto [w, v] = que.front();
        que.pop();
        if(dist[v] < w) continue;
        for(edge &e: g[v]){
          assert(e.wei() == 1);
          weight d = dist[v] + e.wei();
          int to = e.to();
          if(dist[to] > d){
            dist[to] = d;
            par[to] = e;
            que.push(dist_p(d, to));
          }
        }
      }
    }
    vec<edge> get_path(int v){
      assert(!dist.empty());
      vec<edge> ret;
      while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();
      std::reverse(ret.begin(), ret.end());
      return ret;
    }
    weight operator [](int v){return dist[v];}
  };

  // O(V + E)
  // 辺の重みが0か1
  template<typename edge>
  struct zero_one_bfs_shortest_path{
  private:
    using weight = typename edge::weight;
    vec<vec<edge>> &g;
  public:
    zero_one_bfs_shortest_path(vec<vec<edge>> &g): g(g){}
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
    vec<weight> dist;
    vec<edge> par;
    void build(int s){
      int n = g.size();
      if(dist.empty()){
        dist.resize(n, inf);
        par.resize(n, edge{});
      }else{
        std::fill(dist.begin(), dist.end(), inf);
        std::fill(par.begin(), par.end(), edge{});
      }
      std::queue<int> que0, que1;
      dist[s] = edge::z();
      weight dcur = dist[s];
      que0.push(s);
      while(!que0.empty() || !que1.empty()){
        if(que0.empty()){
          std::swap(que0, que1);
          dcur++;
        }
        int v = que0.front();
        que0.pop();
        if(dist[v] < dcur) continue;
        for(edge &e: g[v]){
          weight w = e.wei();
          assert(w == 0 || w == 1);
          weight d = dist[v] + w;
          if(dist[e.t] > d){
            dist[e.t] = d;
            par[e.t] = e;
            if(w == 0) que0.push(e.t);
            else que1.push(e.t);
          }
        }
      }
    }
    vec<edge> get_path(int v){
      assert(!dist.empty());
      vec<edge> ret;
      while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();
      std::reverse(ret.begin(), ret.end());
      return ret;
    }
    weight operator [](int v){return dist[v];}
  };

  // O((V + E)logV)
  // 辺の重みが非負(負の閉路がなければ一応動く)
  template<typename edge>
  struct dijkstra{
  private:
    using weight = typename edge::weight;
    using dist_p = std::pair<weight, int>;
    vec<vec<edge>> &g;
  public:
    dijkstra(vec<vec<edge>> &g): g(g){}
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
    vec<weight> dist;
    vec<edge> par;
    void build(int s){
      int n = g.size();
      if(dist.empty()){
        dist.resize(n, inf);
        par.resize(n, edge{});
      }else{
        std::fill(dist.begin(), dist.end(), inf);
        std::fill(par.begin(), par.end(), edge{});
      }
      std::priority_queue<dist_p, vec<dist_p>, std::greater<dist_p>> que;
      dist[s] = edge::z();
      que.push(dist_p(edge::z(), s));
      while(!que.empty()){
        auto [w, v] = que.top();
        que.pop();
        if(dist[v] < w) continue;
        for(edge &e: g[v]){
          weight d = dist[v] + e.wei();
          int to = e.to();
          if(dist[to] > d){
            dist[to] = d;
            par[to] = e;
            que.push(dist_p(d, to));
          }
        }
      }
    }
    vec<edge> get_path(int v){
      assert(!dist.empty());
      vec<edge> ret;
      while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();
      std::reverse(ret.begin(), ret.end());
      return ret;
    }
    weight operator [](int v){return dist[v];}
  };

  // O(VE)
  // inf: 到達不可, minf: 負の閉路
  template<typename edge>
  struct bellman_ford{
  private:
    using weight = typename edge::weight;
    using dist_p = std::pair<weight, int>;
    vec<vec<edge>> &g;
  public:
    bellman_ford(vec<vec<edge>> &g): g(g){}
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
    vec<weight> dist;
    vec<edge> par;

    void build(int s){
      int n = g.size();
      if(dist.empty()){
        dist.resize(n, inf);
        par.resize(n);
      }else{
        std::fill(dist.begin(), dist.end(), inf);
        std::fill(par.begin(), par.end(), edge{});
      }
      dist[s] = edge::z();
      for(int lp = 0; ; lp++){
        bool update = false;
        for(int i = 0; i < n; i++){
          if(dist[i] == inf) continue;
          for(edge e : g[i]){
            weight &dto = dist[e.to()];
            if(dto == minf){
              if(dto != minf) update = true;
              dto = minf;
            }else if(dto == inf || dto > dist[i] + e.wei()){
              dto = (lp > n ? minf : dist[i] + e.wei());
              par[e.to()] = e;
              update = true;
            }
          }
        }
        if(!update) break;
      }
    }
    vec<edge> get_path(int v){
      assert(!dist.empty());
      vec<edge> ret;
      while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();
      std::reverse(ret.begin(), ret.end());
      return ret;
    }
    weight operator [](int v){return dist[v];}
  };

  // O(V^3)
  template<typename edge>
  struct warshall_floyd{
  private:
    using weight = typename edge::weight;
    vec<vec<edge>> &g;
  public:
    warshall_floyd(vec<vec<edge>> &g): g(g){}
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    static constexpr weight minf = std::numeric_limits<weight>::min() / 2;
    vec<vec<weight>> dist;
    void build(){
      int n = g.size();
      dist.resize(n, vec<weight>(n, inf));
      for(int i = 0; i < n; i++){
        dist[i][i] = 0;
        for(edge &e : g[i]){
          dist[i][e.to()] = std::min(dist[i][e.to()], e.wei());
        }
      }
      for(int k = 0; k < n; k++){
        for(int s = 0; s < n; s++){
          for(int t = 0; t < n; t++){
            dist[s][t] = std::min(dist[s][t], dist[s][k] + dist[k][t]);
          }
        }
      }
    }
    vec<weight>& operator [](int v){return dist[v];}
  };
};

namespace graph_algorithm{
  // {連結成分, DAG}
  template<typename edge>
  std::pair<vec<int>, vec<vec<int>>> scc(vec<vec<edge>> &g){
    int n = g.size();
    vec<int> v(n), cmp(n, 0);
    vec<vec<int>> rg(n), V;
    auto scc_dfs = [&](auto &&scc_dfs, int cur, int &sz)->void{
      cmp[cur] = -1;
      for(edge &e : g[cur]){
        int to = e.to();
        rg[to].push_back(cur);
        if(cmp[to] == 0) scc_dfs(scc_dfs, to, sz);
      }
      v[sz++] = cur;
    };
    auto scc_rdfs = [&](auto &&scc_rdfs, int cur, const int k)->void{
      cmp[cur] = k;
      V[k].push_back(cur);
      for(int to : rg[cur]) if(cmp[to] == -1) scc_rdfs(scc_rdfs, to, k);
    };
    for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) scc_dfs(scc_dfs, i, j);
    for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){
      if(cmp[v[i]] == -1){
        V.push_back(vec<int>());
        scc_rdfs(scc_rdfs, v[i], j++);
      }
    }
    return {cmp, V};
  }
  // {連結成分, 森}
  template<typename edge>
  std::pair<vec<int>, vec<vec<int>>> two_edge_connected(vec<vec<edge>> &g){
    int n = g.size();
    vec<int> v(n), cmp(n, 0);
    vec<vec<int>> V;
    vec<vec<bool>> edge_used(n);
    auto tec_dfs = [&](auto &&tec_dfs, int cur, int &sz)->void{
      cmp[cur] = -1;
      for(int i = 0; i < g[cur].size(); i++){
        int to = g[cur][i].to();
        if(cmp[to] == 0) edge_used[cur][i] = true, tec_dfs(tec_dfs, to, sz);
      }
      v[sz++] = cur;
    };
    auto tec_rdfs = [&](auto &&tec_rdfs, int cur, const int k)->void{
      cmp[cur] = k;
      V[k].push_back(cur);
      for(int i = 0; i < g[cur].size(); i++){
        int to = g[cur][i].to();
        if(cmp[to] == -1 && !edge_used[cur][i]) tec_rdfs(tec_rdfs, to, k);
      }
    };
    for(int i = 0; i < n; i++) edge_used[i].resize(g[i].size(), 0);
    for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) tec_dfs(tec_dfs, i, j);
    for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){
      if(cmp[v[i]] == -1){
        V.push_back(vec<int>());
        tec_rdfs(tec_rdfs, v[i], j++);
      }
    }
    return {cmp, V};
  }
  // 二重頂点連結成分分解
  // {間接点フラグ, 各連結成分が含む頂点}
  template<typename edge>
  std::pair<vec<bool>, vec<vec<int>>> bcc(vec<vec<edge>> &g){
    int n = g.size();
    vec<vec<int>> V;
    vec<int> child(n, 0), dep(n, -1), low(n);
    vec<bool> used(n, false), is_articulation(n, false);
    vec<edge> tmp_edge;
    auto bcc_dfs = [&](auto &&bcc_dfs, int cur, int par, int d)->void{
      if(par != -1) child[par]++;
      dep[cur] = low[cur] = d;
      for(edge &e : g[cur]){
        int to = e.to();
        if(to == par) continue;
        if(dep[to] < dep[cur]) tmp_edge.push_back(e);
        if(dep[e.to()] == -1){
          bcc_dfs(bcc_dfs, to, cur, d + 1);
          if(low[to] >= dep[cur]){
            is_articulation[cur] = true;
            V.push_back(vec<int>());
            bool is_ok = false;
            while(!tmp_edge.empty() && !is_ok){
              edge e = tmp_edge.back();
              tmp_edge.pop_back();
              if(e.from() == cur && e.to() == to) is_ok = true;
              if(!used[e.to()]) V.back().push_back(e.to()), used[e.to()] = true;
              if(!used[e.from()]) V.back().push_back(e.from()), used[e.from()] = true;
            }
            for(int v : V.back()) used[v] = false;
          }
          low[cur] = std::min(low[cur], low[to]);
        }else low[cur] = std::min(low[cur], dep[to]);
      }
    };
    for(int i = 0; i < n; i++){
      if(dep[i] != -1) continue;
      int vsz_pre = V.size();
      bcc_dfs(bcc_dfs, i, -1, 0);
      is_articulation[i] = (child[i] > 1);
      if(V.size() == vsz_pre) V.push_back(vec<int>{i});// 孤立点
    }
    return {is_articulation, V};
  }
  template<typename edge>
  std::tuple<vec<bool>, vec<int>, vec<vec<simple_edge<int>>>> block_cut_tree(vec<vec<edge>> &g){
    auto [is_articulation, V] = bcc<edge>(g);
    int n = g.size();
    vec<int> cmp(n, -1);
    int m = V.size(), a = m;
    for(int i = 0; i < m; i++){
      for(int v : V[i]){
        if(is_articulation[v]) cmp[v] = a++;
        else cmp[v] = i;
      }
    }
    vec<vec<simple_edge<int>>> G(a);
    for(int i = 0; i < m; i++){
      for(int v : V[i]){
        if(is_articulation[v]){
          G[i].push_back({i, cmp[v]});
          G[cmp[v]].push_back({cmp[v], i});
        }
      }
    }
    return {is_articulation, cmp, G};
  }
};
namespace graph_algorithm{
  // 終了時にinが0でない要素がある -> 閉路が存在する
  // 閉路があるなら空のvectorを返す
  template<typename edge>
  vec<int> topological_sort(vec<vec<edge>> &g){
    int n = g.size();
    std::queue<int> que;
    vec<int> in(n, 0), ret;
    for(int i = 0; i < n; i++) for(edge e : g[i]) in[e.to()]++;
    for(int i = 0; i < n; i++) if(!in[i]) que.push(i);
    while(!que.empty()){
      int p = que.front();
      que.pop();
      ret.push_back(p);
      for(edge &e : g[p]){
        int to = e.to();
        if(!(--in[to])) que.push(to);
      }
    }
    for(int i = 0; i < n; i++) if(in[i] != 0) return {};
    return ret;
  }

  // プリム法, 連結なら始点sは関係ない
  template<typename edge>
  vec<edge> undirected_mst(vec<vec<edge>> &g, int s = 0){
    int n = g.size();
    assert(s < n);
    static vec<bool> V(n, 0);
    vec<edge> ret;
    using pde = std::pair<typename edge::weight, edge>;
    std::priority_queue<pde, vec<pde>, std::function<bool(pde, pde)>> que([](pde a, pde b){
      return a.first > b.first;
    });
    V[s] = true;
    for(edge &e : g[s]) que.push(pde{e.wei(), e});
    while(!que.empty()){
      auto [d, e] = que.top();
      que.pop();
      if(V[e.to()]) continue;
      V[e.to()] = true;
      ret.push_back(e);
      for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
    }
    for(edge &e : ret) V[e.to()] = V[e.from()] = false;
    return ret;
  }
  // rを根とするbfs木O(V + E)
  template<typename edge>
  vec<vec<edge>> bfs_tree(vec<vec<edge>> &g, int r){
    int n = g.size();
    std::queue<int> que;
    vec<bool> used(n, false);
    que.push(r);
    vec<vec<edge>> ret(n);
    used[r] = true;
    while(!que.empty()){
      int v = que.front();
      que.pop();
      for(edge &e : g[v]){
        int to = e.to();
        if(used[to]) continue;
        used[to] = true;
        ret[v].push_back(e);
        que.push(to);
      }
    }
    return ret;
  }
  // rを根とするbfs木, 最短経路的 O((V + E)logV)
  // {木, 重みのテーブル}
  template<typename edge>
  std::pair<vec<vec<edge>>, vec<typename edge::weight>> bfs_tree_shortest(vec<vec<edge>> &g, int r){
    int n = g.size();
    using weight = typename edge::weight;
    using pdv = std::pair<weight, int>;
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> que;
    vec<weight> dist(n, inf);
    dist[r] = edge::z();
    que.push({edge::z(), r});

    vec<vec<edge>> pedge(n);
    vec<vec<edge>> ret(n);

    while(!que.empty()){
      auto [d, v] = que.top();
      que.pop();
      if(dist[v] < d) continue;
      for(edge &e : g[v]){
        int to = e.to();
        weight nxtd = d + e.wei();
        if(dist[to] > nxtd){
          dist[to] = nxtd;
          if(!pedge[to].empty()) pedge[to].pop_back();
          pedge[to].push_back(e);
          que.push({nxtd, to});
        }
      }
    }
    for(int i = 0; i < n; i++){
      if(!pedge[i].empty()){
        edge e = pedge[i][0];
        ret[e.s].push_back(e);
      }
    }
    return {ret, dist};
  }
  // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
  template<typename edge>
  void cmp_edge_arrange(const vec<int> &cmp, vec<vec<edge>> &g){
    int n = g.size();
    for(int i = 0; i < n; i++){
      int m = g[i].size();
      int l = 0, r = m - 1;
      while(l < r){
        while(l < m && cmp[i] == cmp[g[i][l].to()]) l++;
        while(0 < r && cmp[i] == cmp[g[i][r].to()]) r--;
        if(l < r) std::swap(g[i][l], g[i][r]);
      }
    }
  }
};


template<typename edge>
struct general_graph{
  using weight = typename edge::weight;
  template<typename T>
  using vec = std::vector<T>;
  using graph = vec<vec<edge>>;
  using simple_graph = general_graph<simple_edge<int>>;
  int n;
  graph g;
  general_graph(int n): n(n), g(n){}
  general_graph(const vec<vec<edge>> &G): n(G.size()), g(G){}

  void add_edge(int a, edge e){
    g[a].push_back(e);
  }
  graph_algorithm::bfs_shortest_path<edge> bfs_shortest_path(){
    return graph_algorithm::bfs_shortest_path<edge>(g);
  }
  graph_algorithm::zero_one_bfs_shortest_path<edge> zero_one_bfs_shortest_path(){
    return graph_algorithm::zero_one_bfs_shortest_path<edge>(g);
  }
  graph_algorithm::dijkstra<edge> dijkstra(){
    return graph_algorithm::dijkstra<edge>(g);
  }
  graph_algorithm::bellman_ford<edge> bellman_ford(){
    return graph_algorithm::bellman_ford<edge>(g);
  }
  graph_algorithm::warshall_floyd<edge> warshall_floyd(){
    return graph_algorithm::warshall_floyd<edge>(g);
  }
  static simple_graph make_simple_graph(const vec<vec<int>> &G){
    int n = G.size();
    vec<vec<simple_edge<int>>> G2(n);
    for(int i = 0; i < n; i++) for(int j : G[i]) G2[i].push_back(simple_edge<int>(i, j));
    return simple_graph(G2);
  }
  // {連結成分, グラフ} 有向サイクル
  std::pair<vec<int>, simple_graph> scc(){
    vec<int> cmp = graph_algorithm::scc(g).first;
    int m = *std::max_element(cmp.begin(), cmp.end()) + 1;
    vec<vec<int>> G(m);
    for(int i = 0; i < n; i++){
      for(auto &e : g[i]){
        if(cmp[i] != cmp[e.t]){
          G[cmp[i]].push_back(cmp[e.t]);
        }
      }
    }
    for(int i = 0; i < m; i++){
      std::sort(G[i].begin(), G[i].end());
      G[i].erase(std::unique(G[i].begin(), G[i].end()), G[i].end());
    }
    return {cmp, make_simple_graph(G)};
  }
  // {連結成分, グラフ} 1つの辺が消えても連結, 森か木になる
  std::pair<vec<int>, vec<vec<int>>> two_edge_connected(){
    vec<int> cmp = graph_algorithm::two_edge_connected(g).first;
    int m = *std::max_element(cmp.begin(), cmp.end()) + 1;
    vec<vec<int>> G(m);
    for(int i = 0; i < n; i++){
      for(auto &e : g[i]){
        if(cmp[i] != cmp[e.t]){
          G[cmp[i]].push_back(cmp[e.t]);
        }
      }
    }
    return {cmp, G};
  }
  // {関節点フラグ, 各連結成分が含む頂点(関節点は複数の連結成分に含まれる))} 1つの頂点が消えても連結
  std::pair<vec<bool>, vec<vec<int>>> bcc(){
    return graph_algorithm::bcc<edge>(g);
  }
  // {関節点フラグ, cmp, 森} 1つの頂点が消えても連結, 森か木になる
  std::tuple<vec<bool>, vec<int>, vec<vec<edge>>> block_cut_tree(){
    return graph_algorithm::block_cut_tree<edge>(g);
  }
  // 閉路が存在するなら空のvector
  vec<int> topological_sort(){
    return graph_algorithm::topological_sort(g);
  }
  // 最小全域木, グラフが連結ならsの値は関係ない
  vec<edge> undirected_mst(int s = 0){
    return graph_algorithm::undirected_mst<edge>(g, s);
  }
  // rを根とするbfs木O(V + E)
   vec<vec<edge>> bfs_tree(int r){
    return graph_algorithm::bfs_tree(g, r);
  }
  // rを根とするbfs木, rからの最短経路 O((V + E)logV)
  std::pair<vec<vec<edge>>, vec<weight>> bfs_tree_shortest(int r){
    return graph_algorithm::bfs_tree_shortest(g, r);
  }
  // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
  void cmp_edge_arrange(const vec<int> &cmp){
    graph_algorithm::cmp_edge_arrange(cmp, g);
  }
  vec<edge> &operator [](int i){return g[i];}
};

using simple_graph = general_graph<simple_edge<int>>;
template<typename T>
using weighted_graph = general_graph<weighted_edge<T>>;
template<typename T>
using labeled_graph =  general_graph<labeled_edge<T>>;
template<typename T>
using weighted_labeled_graph =  general_graph<weighted_labeled_edge<T>>;



int main(){
  io_init();
  int n, m;
  std::cin >> n >> m;
  simple_graph g(n);
  range(i, 0, m){
    int a, b;
    std::cin >> a >> b;
    a--, b--;
    g.add_edge(a, {a, b});
  }
  auto d = g.dijkstra();
  d.build(0);
  auto D1 = d.dist;
  d.build(n - 2);
  auto D2 = d.dist;
  d.build(n - 1);
  auto D3 = d.dist;

  // 1 - (n - 1) - n - 1
  // 1 - n - (n - 1) - 1

  ll ans1 = (ll)D1[n - 2] + D2[n - 1] + D3[0];
  ll ans2 = (ll)D1[n - 1] + D3[n - 2] + D2[0];
  ans1 = min(ans1, ans2);
  std::cout << (ans1 >= 10000000 ? -1 : ans1) << '\n';
}