#line 2 ".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>
#define all(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#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)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
template<typename T>
using vec = std::vector<T>;
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<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<sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}
#line 2 ".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: edge_base<edge_weight>{
  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: edge_base<edge_weight>{
  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: edge_base<edge_weight>{
  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: edge_base<edge_weight>{
  using weight = edge_weight;
  int s, t, i;
  weight w;
  weighted_labeled_edge(): s(-1), t(-1), i(-1), w(0){}
  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 3 ".lib/graph/tree_algorithm.hpp"

// !
template<typename edge>
void tree_diameter_dfs(int cur, int par, typename edge::weight d, typename edge::weight &dmax, int &vmax, const vec<vec<edge>> &g){
  if(d > dmax) dmax = d, vmax = cur;
  for(edge &e : g[cur]){
    if(e.to() == par) continue;
    tree_diameter_dfs(e.to(), cur, d + e.wei(), dmax, vmax);
  }
}
// {直径, s, t}
template<typename edge>
std::tuple<typename edge::weight, int, int> tree_diameter(const vec<vec<edge>> &g){
  int s = 0, t = 0;
  typename edge::weight d = edge::z();
  tree_diameter_dfs(s, -1, 0, d, t, g);
  s = t, t = 0, d = edge::z();
  tree_diameter_dfs(s, -1, 0, d, t, g);
  return {d, s, t};
}
template<typename edge>
std::tuple<vec<vec<int>>, vec<int>, vec<int>, vec<int>> centroid_decomposition_build(const vec<vec<edge>> &g){
  int n = g.size();
  assert(n);
  vec<vec<int>> G(n);
  std::vector<int> size_i(n, 0), dep_i(n, std::numeric_limits<int>::max()), par_i(n, -1);

  auto add_edge = [&](int p, int c)->void{
    G[p].push_back(c);
    G[c].push_back(p);
    par_i[c] = p;
  };
  auto find_centroid = [&](auto &&find_centroid, int v, int p, const int N, const int8_t rank)->std::pair<int, int>{
    int sz = 1;
    for(edge &e: g[v]){
      if(e.t == p || dep_i[e.t] < rank) continue;
      auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, v, N, rank);
      if(sz_c == -1) return {-1, cent_c};
      size_i[e.t] = sz_c, sz += sz_c;
    }
    //サイズが半分以上になったとき
    if(sz * 2 >= N){
      size_i[v] = N;
      dep_i[v] = rank;
      for(edge &e: g[v]){
        if(e.t == p || dep_i[e.t] < rank) continue;
        auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, -1, size_i[e.t], rank + 1);
        assert(sz_c == -1);
        add_edge(v, cent_c);
      }
      if(p != -1){
        auto [sz_c, cent_c] = find_centroid(find_centroid, p, -1, N - sz, rank + 1);
        assert(sz_c == -1);
        add_edge(v, cent_c);
      }
      return {-1, v};// 重心を発見
    }
    return {sz, -1};
  };
  find_centroid(find_centroid, 0, -1, n, 0);
  return {G, size_i, dep_i, par_i};
}
template<typename edge>
struct hld{
  vec<int> subsize, depth, parent, in, out, head, rev;
  hld(vec<vec<edge>> &g, int root){
    build(g, root);
  }
  void dfs_sz(int cur, int par, int dep, vec<vec<edge>> &g){
    depth[cur] = dep;
    parent[cur] = par;
    subsize[cur] = 1;
    if(g[cur].size() && g[cur][0].to() == par) std::swap(g[cur][0], g[cur].back());
    for(int i = 0; i < g[cur].size(); i++){
      edge &e = g[cur][i];
      if(e.to() == par) continue;
      dfs_sz(e.to(), cur, dep + 1, g);
      subsize[cur] += subsize[e.to()];
      if(subsize[g[cur][0].to()] < subsize[e.to()]) std::swap(g[cur][0], e);
    }
  }
  void dfs_hld(int cur, int par, int &times, vec<vec<edge>> &g){
    in[cur] = times++;
    rev[in[cur]] = cur;
    for(edge &e : g[cur]){
      if(e.to() == par) continue;
      head[e.to()] = (g[cur][0].to() == e.to() ? head[cur] : e.to());
      dfs_hld(e.to(), cur, times, g);
    }
    out[cur] = times;
  }
  void build(vec<vec<edge>> &g, int root){
    int n = g.size();
    subsize.resize(n), depth.resize(n), parent.resize(n);
    in.resize(n), out.resize(n), head.resize(n), rev.resize(n);
    dfs_sz(root, -1, 0, g);
    int t = 0;
    dfs_hld(root, -1, t, g);
  }
  int la(int v, int k){
    if(depth[v] < k) return -1;
    while(true){
      int u = head[v];
      if(in[v] - k >= in[u]) return rev[in[v] - k];
      k -= in[v] - in[u] + 1;
      v = parent[u];
    }
  }
  int lca(int u, int v){
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v);
      if(head[u] == head[v]) return u;
    }
  }
  bool is_ancestor(int u, int v){
    if(depth[u] > depth[v]) std::swap(u, v);
    return u == la(v, depth[v] - depth[u]);
  }
  int kth_vertex_on_path(int u, int v, int k){
    int l = lca(u, v), dlu = depth[u] - depth[l];
    if(dlu > k) return la(u, k);
    k = depth[v] - depth[l] - k + dlu;
    if(k < 0) return -1;
    return la(v, k);
  }
  // hldに基づいて頂点を[0, n), 辺を[1, n)に並び替えた時に, 任意のパスはO(log(n))個の区間になる

  // 頂点[0, n)の中でuの位置
  int index_vertex(int u){
    return in[u];
  }
  // 辺[1, n)の中でe{s, t}の位置, 辺が存在しない場合は-1
  int index_edge(int s, int t){
    if(in[s] > in[t]) std::swap(s, t);
    if(parent[t] != s) return -1;
    return in[s] + 1;
  }
  using path = vec<std::pair<int, int>>;
  // 順序を気にせずO(log(n))個の区間を列挙
  path unordered_path(int u, int v, bool is_edge = false){
    path res;
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v);
      if(head[u] == head[v]) break;
      res.push_back({in[head[v]], in[v] + 1});
    }
    res.push_back({in[u] + is_edge, in[v] + 1});
    return res;
  }
  // {lca->uのパス, lca->vのパス}
  std::pair<path, path> ordered_path(int u, int v, bool is_edge = false){
    bool is_swaped = false;
    std::pair<path, path> res;
    path &a = res.first, &b = res.second;
    for(;; v = parent[head[v]]){
      if(in[u] > in[v]) std::swap(u, v), std::swap(a, b), is_swaped ^= 1;
      if(head[u] == head[v]) break;
      b.push_back({in[head[v]], in[v] + 1});
    }
    b.push_back({in[u] + is_edge, in[v] + 1});
    if(is_swaped) std::swap(a, b);
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    return {a, b};
  }
};
// !
// 部分木のサイズ, 深さ, 親
template<typename edge>
std::tuple<vec<int>, vec<int>, vec<int>> simple_dfs(const vec<vec<edge>> &g, int root){
  int n = g.size();
  vec<int> sz(n, 1), de(n), pa(n);
  auto simple_dfs_f = [&](auto simple_dfs_f, int cur, int par, int dep)->void{
    pa[cur] = par;
    de[cur] = dep;
    for(edge &e : g[cur]){
      if(e.to() == par) continue;
      simple_dfs_f(simple_dfs_f, e.to(), cur, dep + 1);
      sz[cur] += sz[e.to()];
    }
  };
  simple_dfs_f(simple_dfs_f, root, -1, 0);
  return {sz, de, pa};
}

// !
// pre_order 頂点を初めて訪れた時刻を記録
// in_pre: 初めて訪れた時刻
// out_pre: in_pre以降に初めてvより上のノードが現れる時刻, 区間[in_pre, out_pre)は部分木
// rev_pre: in_preの順番に頂点を並び替えた状態
template<typename edge>
struct dfs_order{
  vec<int> subsize, depth, parent;
  vec<int> in_pre, out_pre, rev_pre;// 訪れた順番(サイズN)
  vec<int> in_path, out_path, rev_path;// 戻る辺も考慮する(サイズ2N-1)
  dfs_order(vec<vec<edge>> &g, int root){
    build(g, root);
  }
  void dfs_build_inner(int cur, int par, int dep, int &tpath, int &tpre, vec<vec<edge>> &g){
    depth[cur] = dep;
    parent[cur] = par;
    in_path[cur] = tpath;
    rev_path[tpath++] = cur;
    in_pre[cur] = out_path[cur] = tpre;
    rev_pre[tpre++] = cur;
    for(int i = 0; i < g[cur].size(); i++){
      int to = g[cur][i].to();
      if(to == par) continue;
      dfs_build_inner(to, cur, dep + 1, tpath, tpre, g);
      subsize[cur] += subsize[to];
      out_path[cur] = tpath;
      rev_path[tpath++] = cur;
    }
    out_pre[cur] = tpre;
  }
  void build(vec<vec<edge>> &g, int root){
    int n = g.size();
    depth.resize(n), parent.resize(n), subsize.resize(n, 1);
    in_pre.resize(n), out_pre.resize(n), rev_pre.resize(n);
    in_path.resize(n), out_path.resize(n), rev_path.resize(2 * n - 1);
    int a = 0, b = 0;
    dfs_build_inner(root, -1, 0, a, b, g);
  }
  // vがuの部分木に含まれるか(u自身も部分木)
  bool is_subtree(int u, int v){
    return in_path[u] <= in_path[v] && out_path[v] <= out_path[u];
  }
  // u->vパス(最短経路)にwが含まれるか(端点も含む)
  // vがuの部分木 -> wがuの部分木 && vがwの部分木
  // それ以外 -> wがuかvのどちらかを部分木として含む
  bool is_contained_path(int u, int v, int w){
    if(in_path[u] > in_path[v]) std::swap(u, v);
    if(is_subtree(u, v)) return in_path[u] <= in_path[w] && is_subtree(w, v);
    return is_subtree(w, u) || is_subtree(w, v);
  }
  // [in_pre, out_pre)がuの部分木中に存在する頂点番号
  std::pair<int, int> subtree(int u){
    return {in_pre[u], out_pre[u]};
  }
  /*
  std::pair<int, int> path(){

  }
  */
};

// !
template<typename edge>
struct bfs_order{
  vec<int> parent;
  vec<int> in_bfs, rev_bfs, child_in;
  vec<vec<edge>> &g;
  bfs_order(vec<vec<edge>> &g, int root):g(g){
    build(root);
  }
  // 注: g[v][親]が末尾にswapされる
  void build(int root){
    int n = g.size();
    in_bfs.resize(n);
    rev_bfs.resize(n);
    child_in.resize(n, -1);
    parent.resize(n);
    std::queue<std::pair<int, int>> q;
    q.push({root, -1});
    int t = 0;
    while(!q.empty()){
      auto [v, p] = q.front();
      q.pop();
      parent[v] = p;
      if(child_in[p] == -1) child_in[p] = t;
      rev_bfs[t] = v;
      in_bfs[v] = t++;
      for(int i = 0; i < g[v].size(); i++){
        if(g[v][i].to() == p) std::swap(g[v][i], g[v].back());
        q.push({g[v][i].to(), v});
      }
    }
  }
  // vがuの何番目の子か(0-indexed), 親でない場合-1
  int child_index_find(int u, int v){
    if(parent[v] != u) return -1;
    return in_bfs[v] - child_in[u];
  }
  // e{u, v}を探す
  edge get_edge(int u, int v){
    return g[u][child_index_find(u, v)];
  }
  edge get_parent_edge(int u){
    /*
    // 辺が親->子片方向だと壊れる
    return g[u].back();
    */
    int p = parent[u];
    return g[p][child_index_find(p, u)];
  }
};

template<int (*lca)(int, int), int (*dfs_in)(int), int (*dep)(int)>
std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree_build(vec<int> v){
  if(v.empty()) return {};
  std::sort(v.begin(), v.end(), [&](int a, int b){return dfs_in(a) < dfs_in(b);});
  v.erase(std::unique(v.begin(), v.end()), v.end());
  std::stack<int> st;
  vec<std::pair<int, int>> E;
  vec<int> V;
  st.push(v[0]);
  for(int i = 1; i < v.size(); i++){
    if(v[i] == v[i - 1]) continue;
    int l = lca(v[i], v[i - 1]);
    while(true){
      int c = st.top();
      st.pop();
      if(st.empty() || dep(st.top()) <= dep(l)){
        st.push(l);
        st.push(v[i]);
        if(dep(c) > dep(l)){
          E.push_back({l, c});
          V.push_back(c);
          V.push_back(l);
        }
        break;
      }
      int p = st.top();
      if(dep(c) > dep(p)){
        E.push_back({p, c});
        V.push_back(c), V.push_back(p);
      }
    }
  }
  while(st.size() >= 2){
    int c = st.top();
    st.pop();
    int p = st.top();
    if(c != p) E.push_back({p, c}), V.push_back(c), V.push_back(p);
  }
  if(!st.empty()) V.push_back(st.top());
  std::sort(V.begin(), V.end());
  V.erase(std::unique(V.begin(), V.end()), V.end());
  return {V, E};
}
#line 5 ".lib/graph/tree.hpp"

template<typename edge>
struct tree{
  using weight = typename edge::weight;
  template<typename T>
  using vec = std::vector<T>;
  using graph = vec<vec<edge>>;
  using simple_tree = tree<simple_edge<int>>;
public:
  graph g;
  int n, r;
  vec<int> subsize, depth, parent;
  hld<edge> *hld_p;
  dfs_order<edge> *dfs_p;
  bfs_order<edge> *bfs_p;
  tree(int n, int r = 0): g(n), n(n), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}
  tree(graph &g, int r = 0): g(g), n(g.size()), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}

  void add_edge(int a, edge e){
    assert(0 <= a && a < n);
    g[a].push_back(e);
  }
  void add_dual(int a, int b, edge e){
    assert(0 <= a && a < n);
    g[a].push_back(e);
    g[b].push_back(e.reverse());
  }
  void simple_dfs(){
    auto [s, d, p] = simple_dfs(g, r);
    subsize = s, depth = d, parent = p;
  }
  void hld_build(){
    hld_p = new hld<edge>(g, r);
    subsize = hld_p->subsize, depth = hld_p->depth, parent = hld_p->parent;
  }
  void dfs_build(){
    dfs_p = new dfs_order(g, r);
    subsize = dfs_p->subsize, depth = dfs_p->depth, parent = dfs_p->parent;
  }
  void bfs_build(){
    bfs_p = new bfs_order(g, r);
    parent = bfs_p->parent;
  }
  int lca(int u, int v){
    return hld_p->lca(u, v);
  }
  int la(int u, int k){
    return hld_p->la(u, k);
  }
  int dep(int v){
    return depth[v];
  }
  int par(int v){
    return parent[v];
  }
  int size(int v){
    return subsize[v];
  }
  std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree(vec<int> v){
    static std::function<int(int, int)> dfs_in = [&](int v){return dfs_p->in_pre[v];};
    return lca_tree_build<lca, dfs_in, dep>(v);
  }
  // vがuの何番目の子か(0-indexed), 親でない場合-1
  int child_index_find(int u, int v){
    return bfs_p->child_index_find(u, v);
  }
  // s->tパスの辺
  vec<edge> get_path(int s, int t){
    int l = lca(s, t);
    vec<edge> L, R;
    while(s != l){
      L.push_back(g[s].back());
      s = parent[s];
    }
    while(t != l){
      int p = parent[l];
      R.push_back(g[p][child_index_find(p, l)]);
      l = p;
    }
    std::reverse(R.begin(), R.end());
    L.insert(L.end(), R.begin(), R.end());
    return L;
  }
  // vがuの部分木に含まれるか(u自身も部分木)
  bool is_subtree(int u, int v){
    return dfs_p->is_subtree(u, v);
  }
  // u->vパス(最短経路)にwが含まれるか(端点も含む)
  // vがuの部分木 -> wがuの部分木 && vがwの部分木
  // それ以外 -> wがuかvのどちらかを部分木として含む
  bool is_contained_path(int u, int v, int w){
    return dfs_p->is_contained_path(u, v, w);
  }
  simple_tree centroid_decomposition(){
    auto [G, root, size_i, par_i, dep_i] = centroid_decomposition_build<edge>(g);
    simple_tree res(G, root);
    res.subsize = size_i;
    res.parent = par_i;
    res.depth = dep_i;
    return res;
  }
  vec<edge> &operator [](int i){return g[i];}
};
using simple_tree = tree<simple_edge<int>>;
#line 5 ".lib/graph/graph_algorithm.hpp"

// i-bit目が1 -> 頂点iを使う
long long maximum_independent_set(const vec<long long> &g2, long long rem){
  int n = g2.size();
  if(rem == -1) rem = (1LL << n) - 1;
  long long ret = 0;
  int k = -1, m = -1;
  while(true){
    bool update = false;
    for(int i = 0; i < n; i++){
      if(!((rem >> i) & 1)) continue;
      int s = __builtin_popcountll(rem & g2[i]); //次数
      if(s > m) k = i, m = s;
      if(s <= 1){
        rem &= ~(g2[i] | (1LL << i));
        ret |= (1LL << i), update = true;
      }
    }
    if(!update) break;
    k = -1, m = -1;
  }
  if(rem > 0){
    rem &= ~(1LL << k);
    long long p = maximum_independent_set(g2, rem); //kを使わない
    long long q = maximum_independent_set(g2, rem & ~g2[k]); //kを使う
    if(__builtin_popcountll(p) > __builtin_popcountll(q)) ret |= p;
    else ret |= ((1LL << k) | q);
  }
  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> res;
  using pde = 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;
    res.push_back(e);
    for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
  }
  for(edge &e : res) V[e.to()] = V[e.from()] = false;
  return res;
}
// !
// プリム法
template<typename edge>
vec<vec<edge>> undirected_mst_forest(vec<vec<edge>> &g){
  int n = g.size();
  static vec<bool> V(n, 0);
  vec<vec<edge>> res;
  using pde = 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;
  });
  for(int i = 0; i < n; i++){
    if(V[i]) continue;
    V[i] = true;
    res.push_back(vec<edge>());
    for(edge &e : g[i]) 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;
      res.push_back(e);
      for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
    }
    for(edge &e : res.back()) V[e.to()] = V[e.from()] = false;
  }
  return res;
}

// !
// 終了時にinが0でない要素がある -> 閉路が存在する
template<typename edge>
vec<int> topological_sort(vec<vec<edge>> &g){
  int n = g.size();
  std::queue<int> que;
  vec<int> in(n, 0), res;
  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();
    res.push_back(p);
    for(edge &e : g[p]){
      int to = e.to();
      if(!(--in[to])) que.push(to);
    }
  }
  return res;
}

template<typename edge>
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>
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>
pair<vec<int>, 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 {child, V};
}

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

// !
// rを根とするbfs木, 重みを気にしない O(V + E)
template<typename edge>
tree<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);
  tree<edge> res(n, r);
  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;
      res.add_edge(v, e);
      que.push(to);
    }
  }
  return res;
}

// !
// rを根とするbfs木, 最短経路的 O((V + E)logV)
// {木, 重みのテーブル}
template<typename edge>
std::pair<tree<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});
  tree<edge> res(n, r);
  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;
        res.add_edge(v, e);
        que.push({nxtd, to});
      }
    }
  }
  return {res, dist};
}

// O((V + E)logV)
// 辺の重みが非負
template<typename edge>
struct dijkstra{
private:
  using weight = typename edge::weight;
  using dist_p = 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> res;
    while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
    std::reverse(res.begin(), res.end());
    return res;
  }
  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 = 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> res;
    while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
    std::reverse(res.begin(), res.end());
    return res;
  }
  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];}
};
#line 5 ".lib/graph/graph.hpp"

/*
template<typename edge = int, typename dist = int, typename edge_type = simple_edge<edge, dist>>
struct dense_graph{

};
*/
template<typename edge>
struct general_graph{
  using weight = typename edge::weight;
  template<typename T>
  using vec = std::vector<T>;
  using graph = vec<vec<edge>>;
  int n;
  graph g;
  general_graph(int n): n(n), g(n){}

  void add_edge(int a, edge e){
    g[a].push_back(e);
  }

  // i-bit目が1 -> 頂点iを使う
  long long maximum_independent_set(){
    assert(n <= 62);
    vec<long long> g2(n, 0);
    for(int i = 0; i < n; i++) for(edge &e : g[i]) g2[i] |= (1LL << e.to());
    return maximum_independent_set(g2, -1);
  }

  // !
  vec<edge> undirected_mst_build(int s = 0){
    return undirected_mst<edge>(g, s);
  }
  // 終了時にinが0でない要素がある -> 閉路が存在する
  vec<int> topological_sort(){
    return topological_sort(g);
  }
  pair<vec<int>, vec<vec<int>>> scc(){
    return scc(g);
  }
  pair<vec<int>, vec<vec<int>>> two_edge_connected_build(){
    return two_edge_connected<edge>(g);
  }
  pair<vec<int>, vec<vec<int>>> bcc_build(){
    return bcc<edge>(g);
  }
  // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
  void cmp_edge_arrange(const vec<int> &cmp){
    cmp_edge_arrange(cmp, g);
  }
  // rを根とするbfs木, 重みを気にしない O(V + E)
  tree<edge> bfs_tree(int r){
    return bfs_tree(g, r);
  }
  // rを根とするbfs木, 最短経路的 O((V + E)logV)
  tree<edge> bfs_tree_shortest(int r){
    return bfs_tree_shortest(g, r);
  }
  dijkstra<edge> dijkstra_build(){
    return dijkstra<edge>(g);
  }
  bellman_ford<edge> bellman_ford_build(){
    return bellman_ford<edge>(g);
  }
  warshall_floyd<edge> warshall_floyd_build(){
    return warshall_floyd<edge>(g);
  }

  // O(E)
  // 任意のサイクル bfs木 -> e{s, t}を min(dep[s], dep[t])の昇順に確かめる
  // iを含む任意のサイクル bfs木 -> e{s, t}s, tのいずれかがiの部分木かつlca(s, t)がiより上
  //
  /*
  vec<edge> undirected_cycle(const vec<int> &cmp, int s = 0){
    static vec<bool> order(n, -1);
    vec<edge> res;
  }
  */
};

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 4 ".lib/data_structure/segment_tree/monoid.hpp"

struct point_min_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    return std::min(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};

struct point_add_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};

struct point_max_range_max{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    return std::max(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
};

struct point_add_range_max{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
};

struct point_add_range_sum{
  template<typename T>
  static T id(){
    return 0;
  }
  template<typename T>
  static T update(T a, T b){
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
};

struct point_set_range_composite{
  static constexpr int mod = 998244353;
  template<typename T>
  static T id(){
    return {1, 0, 0};
  }
  template<typename T>
  static T update(T a, T b){
    return b;
  }
  template<typename T>
  static T merge(T a, T b){
    int xy = ((long long)a[0] * b[0]) % mod;
    int ab = ((long long)a[1] * b[0] + b[1]) % mod;
    int ba = ((long long)b[2] * a[0] + a[2]) % mod;
    return {xy, ab, ba};
  }
};

struct range_add_range_sum{
  template<typename T>
  static T id1(){
    return T(0);
  }
  template<typename E>
  static E id2(){
    return E(0);
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return a + b * (r - l);
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_add_range_max{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::min();
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return b * (r - l);
    return a + b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

#line 151 ".lib/data_structure/segment_tree/monoid.hpp"
struct range_affine_range_sum{
  const static long long MOD = 998244353;
  template<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return E{1, 0};
  }
  template<typename T>
  static T merge(T a, T b){
    return (a + b) % MOD;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return (a * b[0] + b[1] * (r - l)) % MOD;
  }
  template<typename E>
  static E propagate(E a, E b){
    return E{(a[0] * b[0]) % MOD, (a[1] * b[0] + b[1]) % MOD};
  }
};
#line 3 ".lib/math/integer.hpp"
#include <cstdint>
#line 8 ".lib/math/integer.hpp"
#include <limits>
#line 10 ".lib/math/integer.hpp"

// a^k >= xとなる最小のa^k
uint64_t ceil_pow(uint64_t x, uint64_t a){
  assert(a > 1);
  if(x == 0) return 1;
  static uint64_t INF = std::numeric_limits<uint64_t>::max();
  if(a == 2){
    uint64_t ret = uint64_t(1) << (63 - __builtin_clzll(x));
    if(ret == x) return x;
    assert(ret <= (INF >> 1));
    return ret << 1;
  }
  if(a > 10){
    uint64_t ret = 1;
    while(true){
      if(ret > x / a) break;
      ret *= a;
    }
    if(ret == x) return ret;
    assert(ret <= INF / a);
    return ret * a;
  }
  static std::vector<std::vector<uint64_t>> pow_table(11);
  if(pow_table[a].empty()){
    uint64_t tmp = 1;
    pow_table[a].push_back(1);
    while(true){
      if(tmp > INF / a) break;
      pow_table[a].push_back(tmp *= a);
    }
  }
  auto itr = std::lower_bound(pow_table[a].begin(), pow_table[a].end(), x);
  assert(itr != pow_table[a].end());
  return *itr;
}

// 2^k >= xとなる最小の2^k
uint64_t ceil_2_pow(uint64_t x){
  return ceil_pow(x, 2);
}

// a^k <= xを満たす最大のa^k
uint64_t floor_pow(uint64_t x, uint64_t a){
  assert(x > 0 && a > 1);
  if(a == 2) return uint64_t(1) << (63 - __builtin_clzll(x));
  if(a > 10){
    uint64_t ret = 1;
    while(true){
      if(ret > x / a) return ret;
      ret *= a;
    }
  }
  static std::vector<std::vector<uint64_t>> pow_table(11);
  static uint64_t INF = std::numeric_limits<uint64_t>::max();
  if(pow_table[a].empty()){
    uint64_t tmp = 1;
    pow_table[a].push_back(1);
    while(true){
      if(tmp > INF / a) break;
      pow_table[a].push_back(tmp *= a);
    }
  }
  return *--std::upper_bound(pow_table[a].begin(), pow_table[a].end(), x);
}



// 10 = 10 * 1 + 0
// 10 =  9 * 1 + 1
// 10 =  8 * 1 + 2
// 10 =  7 * 1 + 3
// 10 =  6 * 1 + 4
// 10 =  5 * 2 = 0
// 10 =  4 * 2 + 2
// 10 =  3 * 3 = 1
// 10 =  2 * 5 + 0
// 10 =  1 * 10 + 10

// 商としてありえる数は高々 2 * √x 通り
// また, [dmin, dmax]が存在して, この区間の数で割った商は全て等しく, 区間に含まれない任意の数で割った商とは異なる
// 可能な組{商, dmin, dmax}を列挙
std::vector<std::array<long long, 3>> divrange(long long x){
  if(x == 1) return {{1, 1, 1}};
  std::vector<std::array<long long, 3>> l{{x, 1, 1}}, r{{1, x, x}};
  int ls = 0, rs = 0;
  long long i = 2;
  for(;i*i<=x;i++){
    long long d = x / i;
    if(l[ls][0] != d) l.push_back({d, i, i}), ls++;
    else l[ls][1] = i;
    if(i * i == x) continue;
    if(r[rs][0] != i) r[rs][1] = d + 1, r.push_back({i, d, d}), rs++;
    else r[rs][2] = x;
  }
  if(l[ls][0] == r[rs][0]) l[ls][2] = r[rs][2], r.pop_back();
  std::reverse(r.begin(), r.end());
  r[0][1] = i;
  l.insert(l.end(), r.begin(), r.end());
  return l;
}

// a ^ k <= xを満たす最大のa
uint64_t kth_root_stable(uint64_t x, uint64_t k){
  if(!x) return 0;
  if(k == 1 || x == 1) return x;
  if(k >= 64) return 1;
  uint64_t l = 1, r = x;
  const static uint64_t threshold = std::numeric_limits<uint64_t>::max();
  while(r - l > 1){
    bool f = false;
    uint64_t mid = l + ((r - l) >> 1), z = 1;
    uint64_t lim = threshold / mid;
    for(int i = 0; i < k; i++){
      if(z > lim){
        f = true;
        break;
      }
      z *= mid;
    }
    if(f | (z > x)) r = mid;
    else l = mid;
  }
  return l;
}

// a^k <= x を満たす最大のa
uint64_t kth_root_fast(uint64_t x, uint64_t k){
  if(x <= 1) return (!k ? 1 : x);
  if(k <= 2) return (k <=1 ? !k ? 1 : x : sqrtl(x));
  if(k >= 64||!(x >> k)) return 1;
  const static int sz[8] = {40, 31, 27, 24, 22, 21, 20, 19};
  static std::vector<std::vector<uint64_t>> table;
  if(table.empty()){
    table.resize(40);
    for(int i = 0; i < 40; i++){
      for(uint64_t j = 0; j < 8 && sz[j] > i; j++){
        table[i].push_back((!i ? 1 : table[i - 1][j]) *(j + 3));
      }
    }
  }
  if(k >= 19){
    int ans = 10;
    for(;ans > 2; ans--){
      if(sz[ans - 3]<k || table[k - 1][ans - 3] > x) continue;
      return ans;
    }
    return 2;
  }
  uint64_t r = (k != 3 ? pow(x, (1.0 + 1e-6) / k) : cbrt(x) + 1);
  const static uint64_t threshold = std::numeric_limits<uint64_t>::max();
  while(true){
    uint64_t lim = threshold / r, z = 1;
    for(int i = 0; i < k; i++, z *= r) if(z > lim) goto upper;
    if(z > x) upper: r--;
    else break;
  }
  return r;
}


namespace prime_sieve{
  std::vector<int> primes, min_factor;// 素数, 各数を割り切る最小の素数
  // O(MAX_N loglog MAX_N)
  void init(int MAX_N){
    min_factor.resize(MAX_N + 1, -1);
    for(int i = 2; i <= MAX_N; i++){
      if(min_factor[i] == -1){
        primes.push_back(i);
        min_factor[i] = i;
      }
      for(int p : primes){
        if((long long)p * i > MAX_N || p > min_factor[i]) break;
        min_factor[p * i] = p;
      }
    }
  }
  bool is_prime(int n){
    assert(n < min_factor.size());
    return n == min_factor[n];
  }
  // {{素因数, 数}}, O(log n)
  std::vector<std::pair<int, int>> factorize(int n){
    assert(n < min_factor.size());
    std::vector<std::pair<int, int>> ret;
    while(n > 1){
      int cnt = 0, f = min_factor[n];
      while(n % f == 0){
        n /= f;
        cnt++;
      }
      ret.push_back({f, cnt});
    }
    return ret;
  }
  // 約数列挙, O(√n)
  std::vector<int> divisor(int n){
    auto p = factorize(n);
    std::vector<std::vector<int>> x;
    for(int i = 0; i < p.size(); i++){
      x.push_back(std::vector<int>{1});
      for(int j = 0; j < p[i].second; j++) x[i].push_back(x[i][j] * p[i].first);
    }
    int l = 0, r = 1;
    std::vector<int> ret{1};
    for(int i = 0; i < x.size(); i++){
      for(auto e : x[i]){
        for(int j = l; j < r; j++){
          ret.push_back(ret[j] * e);
        }
      }
      l = r;
      r = ret.size();
    }
    return std::vector<int>(ret.begin() + l, ret.end());
  }
};


std::vector<long long> v{1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2095133040,2205403200,2327925600,2793510720,3491888400,4655851200,5587021440,6983776800,10475665200,13967553600,20951330400,27935107200,41902660800,48886437600,64250746560,73329656400,80313433200,97772875200,128501493120,146659312800,160626866400,240940299600,293318625600,321253732800,481880599200,642507465600,963761198400,1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,10108248702552000,1212898443062400,18194847664593600,20216497405104000,24259796886124800,30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000,897612484786617600};

std::vector<long long> ans{1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,216,224,240,256,288,320,336,360,384,400,432,448,480,504,512,576,600,640,672,720,768,800,864,896,960,1008,1024,1152,1200,1280,1344,1440,1536,1600,1680,1728,1792,1920,2016,2048,2304,2400,2688,2880,3072,3360,3456,3584,3600,3840,4032,4096,4320,4608,4800,5040,5376,5760,6144,6720,6912,7168,7200,7680,8064,8192,8640,9216,10080,10368,10752,11520,12288,12960,13440,13824,14336,14400,15360,16128,16384,17280,18432,20160,20736,21504,23040,24576,25920,26880,27648,28672,28800,30720,32256,32768,34560,36864,40320,41472,43008,46080,48384,49152,51840,53760,55296,57600,61440,62208,64512,65536,69120,73728,80640,82944,86016,92160,96768,98304,103680
};

// 高度合成数(N以下の数の中で最も多い約数を持つ数)
// {N以下の高度合成数, その約数}
std::pair<long long, long long> highly_composite_number(long long N){
  assert(0 < N && N <= 1000000000000000000);
  int idx = upper_bound(v.begin(), v.end(), N) - v.begin() - 1;
  assert(idx != 0);
  return {v[idx], ans[idx]};
}
#line 9 ".lib/data_structure/segment_tree/dual_segment_tree.hpp"


// 区間set, これまでにsetした物の中ならどれかを取得
struct range_set_get_any{
  template<typename Val>
  static Val id1(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy id2(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy propagate(Lazy l, Lazy x){
    return (x == nullptr ? l : x);
  }
  template<typename Val, typename Lazy>
  static Val apply(Val v, Lazy x, int l, int r){
    return (x == nullptr ? v : x);
  }
};

template<typename commutative_group, typename Val, typename Lazy>
struct dual_segment_tree{
  int N, M;
  std::vector<Val> val;
  std::vector<Lazy> lazy;

  dual_segment_tree(){}
  dual_segment_tree(int n): N(n), M(ceil_2_pow(N)),
  val(n, commutative_group::template id1<Val>()), lazy(2 * M - 1, commutative_group::template id2<Lazy>()){}
  dual_segment_tree(int n, Val v): N(n), M(ceil_2_pow(N)),
  val(n, v), lazy(2 * M - 1, commutative_group::template id2<Lazy>()){}
  dual_segment_tree(const std::vector<Val> v):N(v.size()), M(ceil_2_pow(N)),
  val(v), lazy(2 * M - 1, commutative_group::template id2<Lazy>()){}

  Val get(int k){
    assert(0 <= k && k < N);
    int t = k;
    t += M - 1;
    Lazy lz = lazy[t];
    while(t){
      t = (t - 1) >> 1;
      lz = commutative_group::template propagate<Lazy>(lz, lazy[t]);
    }
    return commutative_group::apply(val[k], lz, k, k + 1);
  }
  void update(int l, int r, Lazy x){
    l = std::max(l, 0), r = std::min(r, N);
    assert(l <= r);
    l += M, r += M;
    while(l < r){
      if(l & 1) lazy[l - 1] = commutative_group::template propagate<Lazy>(lazy[l - 1], x), l++;
      if(r & 1) r--, lazy[r - 1] = commutative_group::template propagate<Lazy>(lazy[r - 1], x);
      l >>= 1;
      r >>= 1;
    }
  }
};
#line 6 ".lib/graph/cycle.hpp"

// O(V + E)
// ショートカットが無い閉路を1つ返す, 閉路が無い場合は空のvector
// 自己辺はサイクルと見なさない(含めたい場合, e.from = e.toの辺を探す)
// 多重辺があっても良い
// 無向辺の場合辺にidをつけて逆流しないようにする
template<typename edge>
void cycle_detection_any_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_detection_any_noshortcut<edge>(e.to(), g, use, in, E, res, e.id());
      E.pop_back();
    }
  }
  use[cur] = true;
  in[cur] = -1;
}

template<typename edge>
vec<edge> cycle_detection_any_noshortcut(vec<vec<edge>> &g){
  int n = g.size();
  //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_detection_any_noshortcut<edge>(i, g, use, in, E, res, -1);
    if(!res.empty()) break;
  }
  return res;
}
// !
// vを含む閉路を1つ返す O(V + E)
// 無向辺の場合辺にidをつけて逆流しないようにする
template<typename edge>
vec<edge> cycle_detection_v(vec<vec<edge>> &g, int v){
  int n = g.size();
  vec<edge> E;
  vec<bool> used(n, false);
  bool is_end = false;
  auto cycle_dfs = [&](auto &&cycle_dfs, int cur, int last_edge_id)->void{
    used[cur] = true;
    for(edge &e : g[cur]){
      //if(last_edge_id != -1 && last_edge_id == e.id()) continue; 自己辺もサイクルと見なす場合
      if(e.to() == cur || last_edge_id != -1 && last_edge_id == e.id()) continue;
      if(e.to() == v){
        E.push_back(e);
        is_end = true;
        return;
      }
      if(used[e.to()]) continue;
      E.push_back(e);
      cycle_dfs(cycle_dfs, e.to(), e.id());
      if(is_end) return;
      E.pop_back();
    }
  };
  cycle_dfs(cycle_dfs, v, -1);
  return E;
}

/*
template<typename edge>
vec<edge> directed_cycle_detection_v_noshortcut(vec<vec<edge>> &g, int v){

}
*/

template<typename edge>
vec<edge> undirected_cycle_detection_v_noshortcut(vec<vec<edge>> &g, int v){
  int n = g.size();
  auto E = cycle_detection_v<edge>(g, v);
  if(E.empty()) return E;
  vec<int> in(n, -1);
  for(int i = 0; i < E.size(); i++) in[E[i].from()] = i;
  vec<edge> res;
  int s = v, last_edge_id = E.back().id();
  while(true){
    int next_in = in[s] + 1;
    edge next_e = E[in[s]];
    for(edge &e : g[s]){
      if(in[e.to()] == -1 || e.id() == last_edge_id) continue;
      //if(e.to() == v){自己辺を含む場合
      if(e.to() != s && e.to() == v){// 終了
        res.push_back(e);
        return res;
      }
      if(in[e.to()] > next_in){
        next_in = in[e.to()];
        next_e = e;
      }
    }
    res.push_back(next_e);
    s = next_e.to();
    last_edge_id = next_e.id();
  }
}

// ! グラフが連結でない場合

// res[v] := vを含む閉路 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;
}

//
template<typename edge>
std::pair<typename edge::weight, vec<edge>> mincost_cycle_fast(const vec<vec<edge>> &g, bool directed){
  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>> que;
  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();});

  weight ans = inf;
  vec<edge> E;
  for(int v = n - 1; v >= 0; v--){
    vec<weight> dist(v + 1, inf);
    dist[v] = edge::z();
    que.push({edge::z(), v});
    vec<edge> par(v), unused;
    while(!que.empty()){
      auto [d, u] = que.top();
      que.pop();
      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];
          que.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(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(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};
}
#line 5 "a.cpp"

int main(){
  io_init();
  int t;
  std::cin >> t;
  int n, m;
  std::cin >> n >> m;
  weighted_labeled_graph<ll> g(n);

  range(i, 0, m){
    int a, b, c;
    std::cin >> a >> b >> c;
    a--, b--;
    g.add_edge(a, {a, b, c, i});
    if(!t) g.add_edge(b, {b, a, c, i});
  }
  auto [ans, E] = mincost_cycle_fast(g.g, t);
  std::cout << ans << '\n';

  //for(auto &e : E) std::cout << e.from() << " " << e.to() << " " << e.wei() << '\n';
}