#line 1 ".lib/template.hpp"


#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;
}
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;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

#line 1 ".lib/graph/graph.hpp"


#line 1 ".lib/graph/edge.hpp"


/*
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};}
};

#line 1 ".lib/graph/graph_algorithm.hpp"


#line 7 ".lib/graph/graph_algorithm.hpp"
#include <limits>
#line 9 ".lib/graph/graph_algorithm.hpp"

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]);
      }
    }
  }
};

#line 7 ".lib/graph/graph.hpp"

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());
    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<edge>>> two_edge_connected(){
    vec<int> cmp = graph_algorithm::scc(g).first;
    int m = *std::max_element(cmp.begin(), cmp.end());
    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>>;


#line 1 ".lib/graph/graph_algorithm_cycle.hpp"


#line 7 ".lib/graph/graph_algorithm_cycle.hpp"
//#include "tree.hpp"
//#include "../data_structure/segment_tree/dual_segment_tree.hpp"

namespace graph_algorithm{
  template<typename T>
  using vec = std::vector<T>;
  // O(V + E)
  // ショートカットが無い閉路を1つ返す, 閉路が無い場合は空のvector
  // 自己辺はサイクルと見なさない(含めたい場合, e.from = e.toの辺を探す)
  // 多重辺があっても良い
  // 無向辺の場合辺にidをつけて逆流しないようにする
  template<typename edge>
  void cycle_noshortcut(int cur, vec<vec<edge>> &g, vec<bool> &use, vec<int> &in, vec<edge> &E, vec<edge> &res, int last_edge_id){
    if(in[cur] >= 0){
      int s = 0;
      while(E[s].from() != cur) s++;// cur->curの閉路
      std::queue<edge> shortcut;
      std::fill(use.begin(), use.end(), 0);
      while(res.empty()){
        use[cur] = true;
        int skip_in = -1, end_in = -1;
        edge skip_e = g[cur][0], end_e = g[cur][0];
        for(edge &e : g[cur]){
          int to = e.to();
          if(in[to] == -1 || (last_edge_id == e.id())) continue;
          if(in[to] > in[cur] && skip_in < in[to]) skip_in = in[to], skip_e = e;
          if(in[to] < in[cur] && use[to] && end_in < in[to]) end_in = in[to], end_e = e;
        }
        if(end_in != -1){
          int to = end_e.to();
          while(E[s].from() != to) s++;
          while(E.back().to() != cur) E.pop_back();
          while(!shortcut.empty() && in[shortcut.front().to()] <= in[to]) shortcut.pop();
          E.push_back(end_e);
          while(s != E.size()){
            int srank = (shortcut.empty() ? g.size() : in[shortcut.front().from()]);
            while(s != E.size() && in[E[s].from()] < srank) res.push_back(E[s++]);
            if(!shortcut.empty()){
              int trank = in[shortcut.front().to()];
              res.push_back(shortcut.front());
              shortcut.pop();
              while(in[E[s].from()] < trank) s++;
            }
          }
          return;
        }
        if(in[cur] + 1 != skip_in) shortcut.push(skip_e);
        cur = skip_e.to();
        last_edge_id = skip_e.id();
      }
      return;
    }
    in[cur] = E.size();
    for(edge &e : g[cur]){
      if(e.to() == cur) continue;
      if(!use[e.to()] && res.empty() && (e.id() == -1 || e.id() != last_edge_id)){
        E.push_back(e);
        cycle_noshortcut<edge>(e.to(), g, use, in, E, res, e.id());
        E.pop_back();
      }
    }
    use[cur] = true;
    in[cur] = -1;
  }
  // accept_self_loop := trueなら自己辺も長さ1のサイクルとみなす
  template<typename edge>
  vec<edge> cycle_noshortcut(vec<vec<edge>> &g, bool accept_self_loop){
    int n = g.size();
    if(accept_self_loop){
      for(int i = 0; i < n; i++){
        for(auto &e : g[i]){
          if(e.to() == e.from()){
            return {e}; // 自己辺をサイクルと見なすか
          }
        }
      }
    }
    vec<bool> use(n, false);
    vec<int> in(n, -1);
    vec<edge> res, E;
    for(int i = 0; i < n; i++){
      if(use[i]) continue;
      cycle_noshortcut<edge>(i, g, use, in, E, res, -1);
      if(!res.empty()) break;
    }
    return res;
  }

  // 全体の最小コスト閉路
  // 重みあり  O(V(V + E)logV)
  // 重みなし  O(V(V + E))
  template<typename edge>
  std::pair<typename edge::weight, vec<edge>> cycle_mincost(const vec<vec<edge>> &g, bool directed, bool weighted, bool accept_self_loop){
    using weight = typename edge::weight;
    using pdv = std::pair<weight, int>;
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;
    auto chmin = [&](weight &a, weight b)->bool{
      if(a > b){
        a = b;
        return true;
      }
      return false;
    };
    int n = g.size();
    vec<vec<edge>> cpg = g;
    for(int v = 0; v < n; v++) std::sort(cpg[v].begin(), cpg[v].end(), [](edge &a, edge &b){return a.to() < b.to();});

    std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1;
    std::queue<pdv> q2;
    std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;};
    std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);};
    std::function<bool()> empty = [&]()->bool{return q1.empty();};

    if(!weighted){
      get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;};
      push = [&](pdv a)->void{q2.push(a);};
      empty = [&]()->bool{return q2.empty();};
    }

    weight ans = inf;
    vec<edge> E;
    for(int v = n - 1; v >= 0; v--){
      vec<weight> dist(v + 1, inf);
      dist[v] = edge::z();
      push({edge::z(), v});
      vec<edge> par(v), unused;
      while(!empty()){
        auto [d, u] = get_top();
        if(dist[u] < d) continue;
        for(int i = 0; i < cpg[u].size(); i++){
          int to = cpg[u][i].to();
          if(to > v){
            cpg[u].pop_back();
            continue;
          }
          weight nxtd = d + cpg[u][i].wei();
          if(chmin(dist[to], nxtd)){
            par[to] = cpg[u][i];
            push({nxtd, to});
          }else if(par[u].id() != cpg[u][i].id()) unused.push_back(cpg[u][i]);
        }
      }
      weight pre_ans = ans;
      edge tmp_edge;
      if(!directed){
        for(edge &e : unused){
          if(dist[e.from()] == inf || dist[e.to()] == inf) continue;
          if(e.from() == e.to()){
            if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){
              tmp_edge = e; // 自己辺をサイクルとみなす場合
            }
            continue;
          }
          if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e;
        }
      }else{
        for(edge &e : unused){
          if(dist[e.from()] == inf) continue;
          if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){
            tmp_edge = e; // 自己辺をサイクルとみなす場合
          }
          if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e;
        }
      }
      if(ans < pre_ans){
        E.clear();
        int a = tmp_edge.from();
        while(a != v){
          E.push_back(par[a]);
          a = par[a].from();
        }
        std::reverse(E.begin(), E.end());
        E.push_back(tmp_edge);
        a = tmp_edge.to();
        while(a != v){
          E.push_back(par[a].reverse());
          a = par[a].from();
        }
      }
    }
    return {ans, E};
  }
  // vを含む最小コストの閉路
  // 重みあり O((V + E)logV)
  // 重みなし O(V + E)
  template<typename edge>
  std::pair<typename edge::weight, vec<edge>> cycle_mincost_specific_vertex(vec<vec<edge>> &g, int v, bool directed, bool weighted, bool accept_self_loop){
    using weight = typename edge::weight;
    using pdv = std::pair<weight, int>;
    static constexpr weight inf = std::numeric_limits<weight>::max() / 2;

    auto chmin = [&](weight &a, weight b)->bool{
      if(a > b){
        a = b;
        return true;
      }
      return false;
    };
    int n = g.size();

    std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1;
    std::queue<pdv> q2;
    std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;};
    std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);};
    std::function<bool()> empty = [&]()->bool{return q1.empty();};

    if(!weighted){
      get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;};
      push = [&](pdv a)->void{q2.push(a);};
      empty = [&]()->bool{return q2.empty();};
    }
    weight ans = inf;
    vec<edge> E;

    vec<weight> dist(n, inf);
    dist[v] = edge::z();
    push({edge::z(), v});
    vec<edge> par(n), unused;
    // 無向辺の場合lca(from, to)がvであることがvを含むサイクルになる必要十分条件
    // d1_ancestor[i] := iから辿ってどの深さ1のノードに辿り着くか
    vec<int> d1_ancestor(n, -1);

    while(!empty()){
      auto [d, u] = get_top();
      if(dist[u] < d) continue;
      if(par[u].from() == v) d1_ancestor[u] = u;
      else d1_ancestor[u] = d1_ancestor[par[u].from()];
      for(int i = 0; i < g[u].size(); i++){
        int to = g[u][i].to();
        weight nxtd = d + g[u][i].wei();
        if(chmin(dist[to], nxtd)){
          par[to] = g[u][i];
          push({nxtd, to});
        }else if(par[u].id() != g[u][i].id()) unused.push_back(g[u][i]); //無向辺の逆流対策
      }
    }
    edge tmp_edge;
    if(!directed){
      for(edge &e : unused){
        if(dist[e.from()] == inf || dist[e.to()] == inf) continue;
        if(e.from() == e.to()){
          if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){
            tmp_edge = e; // 自己辺をサイクルと見なす場合
          }
          continue;
        }
        if(d1_ancestor[e.from()] == d1_ancestor[e.to()]) continue;
        if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e;
      }
    }else{
      for(edge &e : unused){
        if(dist[e.from()] == inf) continue;
        if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){
          tmp_edge = e; // 自己辺をサイクルと見なす場合
        }
        if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e;
      }
    }
    if(ans != inf){
      int a = tmp_edge.from();
      while(a != v){
        E.push_back(par[a]);
        a = par[a].from();
      }
      std::reverse(E.begin(), E.end());
      E.push_back(tmp_edge);
      a = tmp_edge.to();
      while(a != v){
        E.push_back(par[a].reverse());
        a = par[a].from();
      }
    }
    return {ans, E};
  }
  // 全ての辺を1度だけ使うウォークが存在するか
  // オイラー路が存在するための必要十分条件
  // 無向グラフ : 奇次数の頂点が2個か0個
  // 有向グラフ : 入次数と出次数の異なる頂点が0個または(2個かつその頂点の間に辺を1本足すと0個にできる)
  // 上の条件を満たさない場合は空のvectorを返す
  // 無向グラフのときは辺にユニークなidを割り振って逆流しないようにする
  template<typename edge>
  vec<edge> eulerian_trail_directed(vec<vec<edge>> g){
    int n = g.size(), m = 0, x = -1, y = -1, z = -1;
    vec<int> in(n, 0), out(n);
    for(int i = 0; i < n; i++){
      out[i] = g[i].size();
      m += out[i];
      for(auto &e : g[i]) in[e.t]++;
    }
    for(int i = 0; i < n; i++){
      if(out[i] > 0) z = i;
      if(in[i] == out[i]) continue;
      if(in[i] > out[i] + 1 || in[i] + 1 < out[i]) return {};
      if(in[i] == out[i] + 1){
        if(y != -1) y = i;
        else return {};
      }
      if(in[i] + 1 == out[i]){
        if(x != -1) x = i;
        else return {};
      }
    }
    if(x != -1) z = x;

    vec<edge> E, E1;
    vec<vec<edge>> E2(n);
    vec<bool> used_vertex(n, false);
    std::queue<int> q;

    // ベースとなるwalkを探す
    auto find_base_walk = [&](int v){
      while(out[v]){
        edge e = g[v].back();
        g[v].pop_back();
        int next = e.t;
        out[v]--;
        in[next]--;
        if(!used_vertex[v]){
          used_vertex[v] = 1;
          q.push(v);
        }
        E1.push_back(e);
        v = next;
      }
      if(!used_vertex[v]){
        used_vertex[v] = 1;
        q.push(v);
      }
    };
    // vから初めてvに帰ってくるサイクルを探す
    auto find_cycle = [&](int v){
      int tmp = v;
      while(out[v]){
        edge e = g[v].back();
        g[v].pop_back();
        int next = e.t;
        in[v]--;
        out[next]--;
        if(!used_vertex[v]){
          used_vertex[v] = 1;
          q.push(v);
        }
        E2[tmp].push_back(e);
        v = next;
      }
    };
    find_base_walk(z);
    while(!q.empty()){
      int tmp = q.front();
      q.pop();
      find_cycle(tmp);
    }
    std::fill(used_vertex.begin(), used_vertex.end(), 0);
    E2[z].insert(E2[z].end(), E1.begin(), E1.end());
    used_vertex[z] = 1;
    auto dfs = [&](auto &&dfs, int cur)->void{
      for(auto &e : E2[cur]){
        E.push_back(e);
        if(!used_vertex[e.t] && e.t != cur){
          dfs(dfs, e.t);
          used_vertex[e.t] = 1;
        }
      }
    };
    dfs(dfs, z);
    if(E.size() != m) return {};// 例: グラフが連結でない場合など
    return E;
  }
  // 辺のidは[0, m)にする
  template<typename edge>
  vec<edge> eulerian_trail_undirected(vec<vec<edge>> g){
    int n = g.size(), m = 0, x = -1, y = -1, z = -1;
    vec<int> deg(n);
    for(int i = 0; i < n; i++){
      deg[i] = g[i].size();
      m += deg[i];
      if(deg[i] & 1){
        if(x == -1) x = i;
        else if(y == -1) y = i;
        else return {};
      }
      if(deg[i]) z = i;
    }
    assert((x == -1 && y == -1) || (x != -1 && y != -1));
    m /= 2;
    if(x != -1) z = x;

    vec<edge> E, E1;
    vec<vec<edge>> E2(n);
    vec<bool> used_edge(m, false), used_vertex(n, false);
    std::queue<int> q;

    // ベースとなるwalkを探す
    auto find_base_walk = [&](int v){
      while(deg[v]){
        edge e = g[v].back();
        g[v].pop_back();
        if(used_edge[e.id()]) continue;
        int next = e.t;
        deg[v]--;
        deg[next]--;
        used_edge[e.id()] = 1;
        if(!used_vertex[v]){
          used_vertex[v] = 1;
          q.push(v);
        }
        E1.push_back(e);
        v = next;
      }
      if(!used_vertex[v]){
        used_vertex[v] = 1;
        q.push(v);
      }
    };
    // vから初めてvに帰ってくるサイクルを探す
    auto find_cycle = [&](int v){
      int tmp = v;
      while(deg[v]){
        edge e = g[v].back();
        g[v].pop_back();
        if(used_edge[e.id()]) continue;
        int next = e.t;
        deg[v]--;
        deg[next]--;
        used_edge[e.id()] = 1;
        if(!used_vertex[v]){
          used_vertex[v] = 1;
          q.push(v);
        }
        E2[tmp].push_back(e);
        v = next;
      }
    };
    find_base_walk(z);
    while(!q.empty()){
      int tmp = q.front();
      q.pop();
      while(deg[tmp]) find_cycle(tmp);
    }
    std::fill(used_vertex.begin(), used_vertex.end(), 0);
    E2[z].insert(E2[z].end(), E1.begin(), E1.end());
    used_vertex[z] = 1;
    auto dfs = [&](auto &&dfs, int cur)->void{
      for(auto &e : E2[cur]){
        E.push_back(e);
        if(!used_vertex[e.t] && e.t != cur){
          dfs(dfs, e.t);
          used_vertex[e.t] = 1;
        }
      }
    };
    dfs(dfs, z);
    if(E.size() != m) return {};// 例: グラフが連結でない場合など
    return E;
  }
  
  /*
  // ! グラフが連結でない場合

  // res[i] := iを含む閉路 O(V^2 + Elog^2V)
  // 全ての辺に[0, E)のuniqueな値を振っておく
  template<typename edge>
  vec<vec<edge>> undirected_cycle_detection_vv(vec<vec<edge>> &g){
    int n = g.size();
    tree<edge> t = bfs_tree<edge>(g, 0);
    vec<bool> used_edge{0};
    for(int i = 0; i < n; i++){
      for(edge &e : t.g[i]){
        assert(0 <= e.id() && e.id() <= 1e7);
        while(used_edge.size() <= e.id()) used_edge.resize(used_edge.size() << 1);
        used_edge[e.id()] = true;
      }
    }
    t.hld_build();
    t.bfs_build();
    dual_segment_tree<range_set_get_any, edge*, edge*> seg(n, nullptr);
    for(int i = 0; i < n; i++){
      for(edge &e : g[i]){
        if(e.id() >= used_edge.size() || !used_edge[e.id()]){// bfs木に含まれない
          for(auto [l, r] : t.hld_p->unordered_path(e.from(), e.to())) seg.update(l, r, &e);
          if(e.id() < used_edge.size()) used_edge[e.id()] = true;
        }
      }
    }
    vec<vec<edge>> res(n);
    for(int i = 0; i < n; i++){
      if(!res[i].empty()) continue;
      edge *e = seg.get(t.hld_p->index_vertex(i));
      if(!e) continue;// iを含む閉路が無い
      vec<edge> E;
      int a = e->from(), b = e->to(), l = t.hld_p->lca(a, b);
      while(a != l){
        E.push_back(t.bfs_p->get_parent_edge(a));
        a = t.parent[a];
      }
      std::reverse(E.begin(), E.end());
      E.push_back(*e);
      while(b != l){
        E.push_back(t.bfs_p->get_parent_edge(b).reverse());
        b = t.parent[b];
      }
      for(edge &e : E) if(res[e.from()].empty()) res[e.from()] = E;
    }
    return res;
  }
  */
};

#line 4 "a.cpp"

int main(){
  io_init();
  // d[x] := 出次数　- 入次数
  int n, m;
  std::cin >> n >> m;
  using edge = weighted_labeled_edge<int>;
  general_graph<edge> g(n);
  range(i, 0, m){
    int a, b;
    std::cin >> a >> b;
    a--, b--;
    g.add_edge(a, {a, b, 1, i});
  }
  vector<int> pos(n, 0);
  vector<edge*> E;
  vector<bool> use(n, false);
  auto f = [&](auto &&f, int cur)->void{
    if(use[cur]){
      while(true){
        edge *e = E.back();
        E.pop_back();
        e->w = 0;
        use[e->s] = false;
        if(e->s == cur) break;
      }
    }
    use[cur] = 1;
    for(; pos[cur] < g[cur].size();){
      use[cur] = 1;
      int to = g[cur][pos[cur]].t, id = g[cur][pos[cur]].i;
      E.push_back(&g[cur][pos[cur]]);
      pos[cur]++;
      f(f, to);
      if(!E.empty() && E.back()->i == id) E.pop_back();
      use[cur] = 0;
    }
    use[cur] = 0;
  };
  range(i, 0, n) f(f, i);
  vector<edge> ans;
  simple_graph g2(n);
  range(i, 0, n){
    for(auto e : g[i]){
      if(e.w){
        ans.push_back(e);
        g2.add_edge(e.s, {e.s, e.t});
      }
    }
  }
  assert(graph_algorithm::cycle_noshortcut(g2.g, true).empty());
  std::cout << n << " " << ans.size() << '\n';
  range(i, 0, ans.size()) std::cout << ans[i].s + 1 << " " << ans[i].t + 1 << '\n';
}