結果
| 問題 |
No.1320 Two Type Min Cost Cycle
|
| コンテスト | |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-05-04 17:47:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 71 ms / 2,000 ms |
| コード長 | 56,508 bytes |
| コンパイル時間 | 2,215 ms |
| コンパイル使用メモリ | 179,920 KB |
| 最終ジャッジ日時 | 2025-02-12 16:55:30 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 57 |
ソースコード
#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 ×, 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;
}
// O(V(V + E)logV)
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);
static constexpr ll inf = std::numeric_limits<ll>::max() / 2;
std::cout << (ans == inf ? -1 : ans) << '\n';
//for(auto &e : E) std::cout << e.from() << " " << e.to() << " " << e.wei() << '\n';
}