/*  Hi,I am warabi. Welcome to my coding space. Let me give you a great word of advice. "The pen is mightier than the sword" -by Edward Bulwer-Lytton   _,,....,,_  _人人人人人人人人人人人人人人人人人人_ -''":::::::::::::`''>   ゆっくりできるとでも?  < ヽ::::::::::::::::::::: ̄^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄  |::::::;ノ´ ̄\:::::::::::\_,. -‐ァ     __   _____   ______  |::::ノ   ヽ、ヽr-r'"´  (.__    ,´ _,, '-´ ̄ ̄`-ゝ 、_ イ、 _,.!イ_  _,.ヘーァ'二ハ二ヽ、へ,_7   'r ´          ヽ、ン、 ::::::rー''7コ-‐'"´    ;  ', `ヽ/`7 ,'==─-      -─==', i r-'ァ'"´/  /! ハ  ハ  !  iヾ_ノ i イ iゝ、イ人レ/_ルヽイ i | !イ´ ,' | /__,.!/ V 、!__ハ  ,' ,ゝ レリイi (ヒ_]     ヒ_ン ).| .|、i .|| `!  !/レi' (ヒ_]     ヒ_ン レ'i ノ   !Y!""  ,___,   "" 「 !ノ i | ,'  ノ   !'"  ,___,  "' i .レ'    L.',. ヽ _ン    L」 ノ| .|  (  ,ハ    ヽ _ン   人!      | ||ヽ、       ,イ| ||イ| / ,.ヘ,)、  )>,、 _____, ,.イ  ハ    レ ル` ー--─ ´ルレ レ´  Take your time.    GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!   */ #include using namespace std; #define ll long long #define ld long double #define V vector #define rep(i,a,b) for(ll i=a;i=b;i--) #define reph(i,vec) for(auto &i:vec) #define FI first #define SE second #define P pair #define PB push_back #define INS insert #define all(vec) vec.begin(),vec.end() #define in(name) ll name;cin >> name #define ins(name) string name;cin >> name; #define inc(name) char name;cin >> name #define ing(name,size,E) vector> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);} #define ing_on(name,size,E) vector> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);} #define ing_cost(name,size,E) vector>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});} #define invll(name,size) vector name(size);reph(i,name)cin >> i #define invvll(name,size1,size2) vector> name(size1,vector(size2));reph(v,name)reph(i,v)cin>>i; #define invp(name,size) vector> name(size);for(ll i=0;i> name[i].FI >> name[i].SE #define out(n) cout << (n) << endl #define _out(n) cout << " " << (n) << endl; #define notout(n) cout << (n) #define out_(n) cout << (n) << " " #define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl; #define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl; #define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " "; #define vout(vec) for(int i=0;i0) #define INF 1000000000000000000 #define MOD 1000000007 #define MOD2 998244353 #define CMOD MOD2 #define EPS 0.00000001 //debug #define bug assert(false); #define debug out("this point ok"); // //constexpr long double PI=3.14159265358979323846; //template template inline bool chmax(T &a,const T b){if(a inline bool chmin(T &a,const T b){if(a>b){a=b;return true;}return false;} // namespace Warabi{ //常備変数のコーナー V primes(3001000,true); V prime_list; V prime_rui(3001000,0LL); V visiteded(300100); V afed(300100,false); V k1(200100,0ll); V k2(200100,0ll); // //常備構造体宣言のコーナー class UnionFind { private: ll NumberOfElements; ll Not1NumberOfelements; public: vector par; vector SIZE; void init(ll sz) { par.resize(sz, -1LL); SIZE.resize(sz,1LL); NumberOfElements=sz; Not1NumberOfelements=0ll; } ll root(ll pos) { if (par[pos] == -1) return pos; par[pos] = root(par[pos]); return par[pos]; } bool same(ll u, ll v) { if (root(u) == root(v)) return true; return false; } ll SZ(ll u){ return SIZE[root(u)]; } ll noe(){ return NumberOfElements; } ll nnoe(){ return Not1NumberOfelements; } bool unite(ll u, ll v) { u = root(u); v = root(v); if (u == v){ return false; } if(SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++; par[u] = v; SIZE[v] += SIZE[u]; NumberOfElements--; return true; } }; class SCC{ public: V> G; V> UG; V order; V GROUP; V visited; ll sz_count; V groupsize; void init(ll sz){ G.resize(sz,V(0)); UG.resize(sz,V(0)); GROUP.resize(sz,-1ll); visited.resize(sz,false); sz_count=0LL; return; } void dfs(ll now){ visited[now]=true; reph(i,G[now]){ if(visited[i])continue; dfs(i); } order.PB(now); return; } void dfs2(ll now,ll group){ GROUP[now]=group; sz_count++; reph(i,UG[now]){ if(GROUP[i]!=-1ll and GROUP[i]!=group)continue; if(GROUP[i]!=-1ll)continue; dfs2(i,group); } return; } void make_group(V> Graph_function){ G=Graph_function; rep(i,0,(ll)G.size()){ reph(j,G[i]){ UG[j].PB(i); } } rep(i,0,(ll)G.size()){ if(visited[i])continue; dfs(i); } reverse(all(order)); ll now_group=0LL; reph(i,order){ if(GROUP[i]!=-1)continue; ll prev=sz_count; dfs2(i,now_group); now_group++; groupsize.PB(sz_count-prev); } return; } }; template class SegmentTree{ public: long long sz; using FX=function; using FA=function; using FM=function; const FX fx; const FA fa; const FM fm; const X ex; const M em; vector node; vector lazy; SegmentTree(long long sz_,FX fx_,FA fa_,FM fm_,X ex_,M em_):sz(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_){ long long n=1LL; while(n=0;i--)node[i]=fx(node[i*2+1],node[i*2+2]); return; } void eval(long long k){ if(lazy[k]==em)return; if(k class multimap{ private: map mp; public: void add(ll x){ mp[x]++; return; } void del(ll x){ mp[x]--; if(mp[x]<1)mp.erase(x); return; } T maximum(){ return mp.rbegin()->first; } T minimum(){ return mp.begin()->first; } }; class LCA{ public: vector> parent; vector dist; vector> G; LCA(const vector> &gr){init(gr);} void dfs(long long v,long long p,long long d){ parent[0][v]=p; dist[v]=d; for(long long next : G[v]){ if(next==p)continue; dfs(next,v,d+1); } return; } void init(const vector> &gr){ G=gr; parent.assign(33,vector(G.size(),-1LL)); dist.assign(G.size(),-1LL); dfs(0LL,-1LL,0LL); for(int i=0;i<32;i++){ for(int j=0;j<(int)G.size();j++){ if(parent[i][j]<0LL){ parent[i+1][j]=-1LL; } else{ parent[i+1][j]=parent[i][parent[i][j]]; } } } return; } long long lca(long long u,long long v){ if(dist[u]=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } assert(parent[0][u]==parent[0][v]); return parent[0][u]; } long long get_dist(long long u,long long v){ return dist[u]+dist[v]-2*dist[lca(u,v)]; } bool on_path(long long u,long long v,long long a){ return get_dist(u,v)==get_dist(u,a)+get_dist(v,a); } }; class nCk { public: const long long m; const long long MAXIMUM = 1000000; vector fac, facinv, inv; nCk(long long m_); ~nCk(); long long com(long long n, long long k)const; long long com_(vector vec)const; }; nCk::nCk(long long m_):m(m_) { fac.resize(MAXIMUM + 3); facinv.resize(MAXIMUM + 3); inv.resize(MAXIMUM + 3); fac[0] = fac[1] = 1; facinv[0] = facinv[1] = 1; inv[1] = 1; for (long long i = 2; i < MAXIMUM + 2; i++) { fac[i] = fac[i - 1] * i % m; inv[i] = m - inv[m % i] * (m / i) % m; facinv[i] = facinv[i - 1] * inv[i] % m; } } nCk::~nCk(){} long long nCk::com(long long n, long long k)const { if(k==0)return 1; if (n < k)return 0LL; assert(!(n < 0 || k < 0)); return fac[n] * (facinv[k] * facinv[n - k] % m) % m; } long long nCk::com_(vector vec)const{ long long sz=(long long)vec.size(); long long sum=0LL; for(const long long v:vec)sum+=v; long long res=1LL; for(long long i=0;i>> G,ll start,bool type){ visiteded=afed; queue sirabe; sirabe.push(start); V short_load(G.size(),0LL); while(!sirabe.empty()){ ll s=sirabe.front(); sirabe.pop(); visiteded[s]=true; reph(i,G[s]){ if(visiteded[i.FI])continue; short_load[i.FI]=short_load[s]+i.SE; sirabe.push(i.FI); } } ll far_max=-1LL; ll element=-1LL; rep(i,0,(ll)G.size()){ if(far_max>=short_load[i])continue; far_max=short_load[i]; element=i; } if(type)return Cdiameter(G,element,false); else return {start,element,far_max}; } //素数の取得 void prime_init(){ V at(3001000,true); primes=at; primes[0]=primes[1]=false; rep(i,2,3000100){ if(!primes[i])continue; for(ll j=i*2;j<=300100;j+=i)primes[j]=false; } rep(i,1,3000100){ if(primes[i]){ prime_list.PB(i); prime_rui[i]=prime_rui[i-1]+1; } else{ prime_rui[i]=prime_rui[i-1]; } } return; } //modpow long long modpow(long long a, long long b, long long m) { long long p = 1, q = a; for (int i = 0; i < 63; i++) { if ((b & (1LL << i)) != 0) { p *= q; p %= m; } q *= q; q %= m; } return p; } //逆元 long long Div(long long a, long long b, long long m) { return (a * modpow(b, m - 2, m)) % m; } //点と点の距離を返す long double Dis(ll ax,ll ay,ll bx,ll by){ return sqrt(pow(ax-bx,2)+pow(ay-by,2)); } //二つのベクトルから平行四辺形の面積を返す ll he(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){//外積を二で割る return abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)); } // template ll Lis_size(V arr,ll sz){ const T TINF=numeric_limits::max(); V DP(sz+1,TINF); DP[0]=-TINF; rep(i,0,sz){ *lower_bound(all(DP),arr[i])=arr[i]; } ll ans=0LL; rep(i,1,sz+1){ if(DP[i]!=TINF)ans=i; } return ans; } string toBinary(ll n){ string r; while (n != 0LL){ r += ( n % 2LL == 0LL ? "0" : "1" ); n /= 2LL; } return r; } template V press(V arr){ V X=arr; sort(all(X)); X.erase(unique(all(X)),X.end()); V ans(arr.size()); rep(i,0LL,(ll)arr.size()){ ans[i]=lower_bound(all(X),arr[i])-X.begin(); } return ans; } P>,V>>> warshall_floyd(ll N,V>> G){ V> DP(N,V(N,INF)); rep(i,0,N)DP[i][i]=0LL; V>> prev(N,V>(N,{INF,INF})); rep(i,0,N){ reph(j,G[i]){ DP[i][j.FI]=j.SE; prev[i][j.FI]={i,j.FI}; } } rep(k,0,N){ rep(i,0,N){ rep(j,0,N){ if(chmin(DP[i][j],DP[i][k]+DP[k][j])){ prev[i][j]=prev[k][j]; } } } } return {DP,prev}; } template void to_sum(V &arr){ rep(i,0,(ll)arr.size()-1LL){ arr[i+1]+=arr[i]; } return; } template void including_map(ll H,ll W,V> &G,T c){ V> new_G(H+2,V(W+2)); rep(i,0,W+2)new_G[0][i]=c; rep(i,1,H+1){ new_G[i][0]=c; new_G[i][W+1]=c; rep(j,1,W+1){ new_G[i][j]=G[i-1][j-1]; } } rep(i,0,W+2)new_G[H+1][i]=c; G=new_G; return; } struct BIT { private: vector bit; int N; public: BIT(int size) { N = size; bit.resize(N + 1); } // 一点更新です void add(int a, int w) { for (int x = a; x <= N; x += x & -x) bit[x] += w; } // 1~Nまでの和を求める。 int sum(int a) { int ret = 0; for (int x = a; x > 0; x -= x & -x) ret += bit[x]; return ret; } }; ll fall_down(ll n,const V &v){ ll ans = 0; BIT b(n); // これまでの数字がどんな風になってるのかをメモる為のBIT for (int i = 0; i < n; i++) { ans += i - b.sum(v[i]); // BITの総和 - 自分より左側 = 自分より右側 b.add(v[i], 1); // 自分の位置に1を足す } return ans; } set factor(ll N){ set ans; for(ll i=1LL;i*i<=N;i++){ if(N%i)continue; ans.INS(i); ans.INS(N/i); } return ans; } V dijkstra(ll sz,V>> G,ll s){ V ans(sz,INF);ans[s]=0LL; priority_queue,vector>,greater>> examine; examine.push({0LL,s}); while(examine.size()){ P p=examine.top(); examine.pop(); ll now=p.SE,dist=p.FI; if(ans[now] pass(const V> &G,ll s,ll t){ V visited(G.size(),false); set ans,res; function dfs=[&](ll now){ visited[now]=true; res.INS(now); if(now==t){ ans=res; } reph(next,G[now]){ if(visited[next])continue; dfs(next); } res.erase(now); return; }; dfs(s); return ans; } // 負の数にも対応した mod (a = -11 とかでも OK) inline long long mod(long long a, long long m) { long long res = a % m; if (res < 0) res += m; return res; } // 拡張 Euclid の互除法 long long extGCD(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGCD(b, a%b, q, p); q -= a/b * p; return d; } long long extGcd(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGcd(b, a%b, q, p); q -= a/b * p; return d; } // 逆元計算 (ここでは a と m が互いに素であることが必要) long long modinv(long long a, long long m) { long long x, y; extGCD(a, m, x, y); return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので } // Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない) // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])" // coeffs[k] = m[0]m[1]...m[k-1] // constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2] long long Garner(vector b, vector m, long long Mmod) { m.push_back(Mmod); // banpei vector coeffs((int)m.size(), 1); vector constants((int)m.size(), 0); for (int k = 0; k < (int)b.size(); ++k) { long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]); for (int i = k+1; i < (int)m.size(); ++i) { (constants[i] += t * coeffs[i]) %= m[i]; (coeffs[i] *= m[k]) %= m[i]; } } return constants.back(); } pair ChineseRem(const vector &b, const vector &m) { long long r = 0, M = 1; for (int i = 0; i < (int)b.size(); ++i) { long long p, q; long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d) if ((b[i] - r) % d != 0) return make_pair(0, -1); long long tmp = (b[i] - r) / d * p % (m[i]/d); r += M * tmp; M *= m[i]/d; } return make_pair(mod(r, M), M); } map bunkai(ll n){ map ans; for(int i=2;i*i<=n;i++){ while(n%i==0){ if(n!=i)ans[n/i]++; n/=i; ans[i]++; } } if(n>1)ans[n]++; return ans; } template void RLE(vector &arr){ vector res; res.push_back(arr[0]); for(const T t:arr){ if(res.back()!=t)res.push_back(t); } arr=res; return; } } // //構造体宣言のコーナー struct P2{ ll l,r; }; bool operator < (P2 a,P2 b){ if(a.r> G(N); V> E; V cnt(N,0ll),dist(N,0ll); rep(i,0,N-1){ in(u);in(v);u--;v--;if(v dfs=[&](ll now,ll par){ reph(next,G[now]){ if(next==par)continue; dist[next]=dist[now]+1; cnt[next]+=cnt[now]; dfs(next,now); } return; }; dfs(0,-1); ll base=0ll; rep(i,0,N-1){ ll u=E[i].FI,v=E[i].SE; if(dist[u]