//todo 文字数を少なくする //#pragma GCC optimize ("-O3") #include using namespace std; //@起動時 struct initon { initon() { cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); srand((unsigned) clock() + (unsigned) time(NULL)); }; } __initon; //衝突対策 #define ws ___ws //@必須構造 struct T { int f, s, t; T() { f = -1, s = -1, t = -1; } T(int f, int s, int t) : f(f), s(s), t(t) {} bool operator<(const T &r) const { return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 大きい順 } bool operator>(const T &r) const { return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順 } bool operator==(const T &r) const { return f == r.f && s == r.s && t == r.t; } bool operator!=(const T &r) const { return f != r.f || s != r.s || t != r.t; } int operator[](int i) { assert(i < 3); return i == 0 ? f : i == 1 ? s : t; } }; struct F { int a, b, c, d; F() { a = -1, b = -1, c = -1, d = -1; } F(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {} bool operator<(const F &r) const { return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; // return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d; } bool operator>(const F &r) const { return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d; // return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; } bool operator==(const F &r) const { return a == r.a && b == r.b && c == r.c && d == r.d; } bool operator!=(const F &r) const { return a != r.a || b != r.b || c != r.c || d != r.d; } int operator[](int i) { assert(i < 4); return i == 0 ? a : i == 1 ? b : i == 2 ? c : d; } }; T mt(int a, int b, int c) { return T(a, b, c); } //@マクロ省略系 型,構造 #define int long long #define ll long long #define double long double #define ull unsigned long long using dou = double; using itn = int; using str = string; using bo= bool; #define au auto using P = pair; #define fi first #define se second #define vec vector #define beg begin #define rbeg rbegin #define con continue #define bre break #define brk break #define is == //マクロ省略系 コンテナ using vi = vector; #define _overloadvvi(_1, _2, _3, _4, name, ...) name #define vvi0() vec #define vvi1(a) vec a #define vvi2(a, b) vec a(b) #define vvi3(a, b, c) vec a(b,vi(c)) #define vvi4(a, b, c, d) vec a(b,vi(c,d)) #define vvi(...) _overloadvvi(__VA_ARGS__,vvi4,vvi3,vvi2 ,vvi1,vvi0)(__VA_ARGS__) using vl = vector; #define _overloadvvl(_1, _2, _3, _4, name, ...) name #define vvl1(a) vec a #define vvl2(a, b) vec a(b) #define vvl3(a, b, c) vec a(b,vl(c)) #define vvl4(a, b, c, d) vec a(b,vl(c,d)) #define vvl(...) _overloadvvl(__VA_ARGS__,vvl4,vvl3,vvl2 ,vvl1)(__VA_ARGS__) using vb = vector; #define _overloadvvb(_1, _2, _3, _4, name, ...) name #define vvb1(a) vec a #define vvb2(a, b) vec a(b) #define vvb3(a, b, c) vec a(b,vb(c)) #define vvb4(a, b, c, d) vec a(b,vb(c,d)) #define vvb(...) _overloadvvb(__VA_ARGS__,vvb4,vvb3,vvb2 ,vvb1)(__VA_ARGS__) using vs = vector; #define _overloadvvs(_1, _2, _3, _4, name, ...) name #define vvs1(a) vec a #define vvs2(a, b) vec a(b) #define vvs3(a, b, c) vec a(b,vs(c)) #define vvs4(a, b, c, d) vec a(b,vs(c,d)) #define vvs(...) _overloadvvs(__VA_ARGS__,vvs4,vvs3,vvs2 ,vvs1)(__VA_ARGS__) using vd = vector; #define _overloadvvd(_1, _2, _3, _4, name, ...) name #define vvd1(a) vec a #define vvd2(a, b) vec a(b) #define vvd3(a, b, c) vec a(b,vd(c)) #define vvd4(a, b, c, d) vec a(b,vd(c,d)) #define vvd(...) _overloadvvd(__VA_ARGS__,vvd4,vvd3,vvd2 ,vvd1)(__VA_ARGS__) using vc=vector; #define _overloadvvc(_1, _2, _3, _4, name, ...) name #define vvc1(a) vec a #define vvc2(a, b) vec a(b) #define vvc3(a, b, c) vec a(b,vc(c)) #define vvc4(a, b, c, d) vec a(b,vc(c,d)) #define vvc(...) _overloadvvc(__VA_ARGS__,vvc4,vvc3,vvc2 ,vvc1)(__VA_ARGS__) using vp = vector

; #define _overloadvvp(_1, _2, _3, _4, name, ...) name #define vvp1(a) vec a #define vvp2(a, b) vec a(b) #define vvp3(a, b, c) vec a(b,vp(c)) #define vvp4(a, b, c, d) vec a(b,vp(c,d)) using vt = vector; #define _overloadvvt(_1, _2, _3, _4, name, ...) name #define vvt1(a) vec a #define vvt2(a, b) vec a(b) #define vvt3(a, b, c) vec a(b,vt(c)) #define vvt4(a, b, c, d) vec a(b,vt(c,d)) #define v3i(a, b, c, d) vector> a(b, vector(c, vi(d))) #define v3d(a, b, c, d) vector> a(b, vector(c, vd(d))) #define v3m(a, b, c, d) vector> a(b, vector(c, vm(d))) #define _vvi vector #define _vvl vector #define _vvb vector #define _vvs vector #define _vvd vector #define _vvc vector #define _vvp vector #define PQ priority_queue, greater > #define tos to_string using mapi = map; using mapd = map; using mapc = map; using maps = map; using seti = set; using setd = set; using setc = set; using sets = set; using qui = queue; #define bset bitset #define uset unordered_set #define mset multiset #define umap unordered_map #define umapi unordered_map #define umapp unordered_map #define mmap multimap //マクロ 繰り返し #define _overloadrep(_1, _2, _3, _4, name, ...) name # define _rep(i, n) for(int i = 0,_lim=n; i < _lim ; i++) #define repi(i, m, n) for(int i = m,_lim=n; i < _lim ; i++) #define repadd(i, m, n, ad) for(int i = m,_lim=n; i < _lim ; i+= ad) #define rep(...) _overloadrep(__VA_ARGS__,repadd,repi,_rep,)(__VA_ARGS__) #define _rer(i, n) for(int i = n; i >= 0 ; i--) #define reri(i, m, n) for(int i = m,_lim=n; i >= _lim ; i--) #define rerdec(i, m, n, dec) for(int i = m,_lim=n; i >= _lim ; i-=dec) #define rer(...) _overloadrep(__VA_ARGS__,rerdec,reri,_rer,)(__VA_ARGS__) #define fora(a, b) for(auto&& a : b) #define forg(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].from, t = ve[gi].to, c = ve[gi].cost, true); gi++) #define fort(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].from, t = ve[gi].to, c = ve[gi].cost, true); gi++)if(t!=p) //#define fort(gi, ve) for (int gi = 0, f, t, c;gi::min(); ll mi = numeric_limits::max(); const int y4[] = {-1, 1, 0, 0}; const int x4[] = {0, 0, -1, 1}; const int y8[] = {0, 1, 0, -1, -1, 1, 1, -1}; const int x8[] = {1, 0, -1, 0, 1, -1, 1, -1}; //マクロ省略形 関数等 #define arsz(a) (sizeof(a)/sizeof(a[0])) #define sz(a) ((int)(a).size()) #define rs resize #define mp make_pair #define pb push_back #define pf push_front #define eb emplace_back #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() //@拡張系 こう出来るべきというもの //埋め込み 存在を意識せずに機能を増やされているもの namespace std { template<> class hash> { public: size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) + x.second); } }; template<> class hash> { public: //大きいllが渡されると、<<32でオーバーフローするがとりあえず問題ないと判断 size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) + x.second); } }; } istream &operator>>(istream &iss, P &a) { iss >> a.first >> a.second; return iss; } template istream &operator>>(istream &iss, vector &vec) { for (T &x: vec) iss >> x; return iss; } ostream &operator<<(ostream &os, P p) { os << p.fi << " " << p.se << endl; return os; } ostream &operator<<(ostream &os, T p) { os << p.f << " " << p.s << " " << p.t; return os; } ostream &operator<<(ostream &os, F p) { os << p.a << " " << p.b << " " << p.c << " " << p.d; return os; } template ostream &operator<<(ostream &os, vector &vec) { for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template ostream &operator<<(ostream &os, vector > &vec) { for (int i = 0; i < vec.size(); i++) { for (int j = 0; j < vec[0].size(); j++) { os << vec[i][j]; } os << endl; } return os; } template void resize(vector &vec, const H head) { vec.resize(head); } template void resize(vector &vec, const H &head, const T ... tail) { vec.resize(head); for (auto &v: vec) resize(v, tail...); } template bool all_of(const vector &vec, _Pr pred) { return std::all_of(vec.begin(), vec.end(), pred); } template bool any_of(const vector &vec, _Pr pred) { return std::any_of(vec.begin(), vec.end(), pred); } template bool none_of(const vector &vec, _Pr pred) { return std::none_of(vec.begin(), vec.end(), pred); } template const typename vector::const_iterator find_if(const vector &vec, _Pr pred) { return std::find_if(vec.begin(), vec.end(), pred); } template bool contains(const vector &vec, const T &val) { return std::find(vec.begin(), vec.end(), val) != vec.end(); } template bool contains_if(const vector &vec, _Pr pred) { return std::find_if(vec.begin(), vec.end(), pred) != vec.end(); } template void replace(vector &a, T key, T v) { replace(a.begin(), a.end(), key, v); } template bool includes(vector &a, vector &b) { vi c = a; vi d = b; sort(all(c)); sort(all(d)); return includes(all(c), all(d)); } template bool is_permutation(vector &a, vector &b) { return is_permutation(all(a), all(b)); } template bool next_permutation(vector &a) { return next_permutation(all(a)); } template T pop(set &set) { T res = *set.begin(); set.erase(set.find(res)); return res; } template T pop(mset &set) { T res = *set.begin(); set.erase(set.find(res)); return res; } template T popBack(set &set) { T res = *set.rbegin(); set.erase(set.find(res)); return res; } template T popBack(mset &set) { T res = *set.rbegin(); set.erase(set.find(res)); return res; } inline void sort(string &a) { sort(a.begin(), a.end()); } template inline void sort(vector &a) { sort(a.begin(), a.end()); }; template inline void sort(vector &a, int len) { sort(a.begin(), a.begin() + len); }; template inline void sort(vector &a, F f) { sort(a.begin(), a.end(), [&](T l, T r) { return f(l) < f(r); }); }; enum ___pcomparator { fisi, fisd, fdsi, fdsd, sifi, sifd, sdfi, sdfd }; inline void sort(vector

&a, ___pcomparator type) { switch (type) { case fisi: sort(all(a), [&](P l, P r) { return l.fi != r.fi ? l.fi < r.fi : l.se < r.se; }); break; case fisd: sort(all(a), [&](P l, P r) { return l.fi != r.fi ? l.fi < r.fi : l.se > r.se; }); break; case fdsi: sort(all(a), [&](P l, P r) { return l.fi != r.fi ? l.fi > r.fi : l.se < r.se; }); break; case fdsd: sort(all(a), [&](P l, P r) { return l.fi != r.fi ? l.fi > r.fi : l.se > r.se; }); break; case sifi: sort(all(a), [&](P l, P r) { return l.se != r.se ? l.se < r.se : l.fi < r.fi; }); break; case sifd: sort(all(a), [&](P l, P r) { return l.se != r.se ? l.se < r.se : l.fi > r.fi; }); break; case sdfi: sort(all(a), [&](P l, P r) { return l.se != r.se ? l.se > r.se : l.fi < r.fi; }); break; case sdfd: sort(all(a), [&](P l, P r) { return l.se != r.se ? l.se > r.se : l.fi > r.fi; }); break; } }; inline void sort(vector &a, ___pcomparator type) { switch (type) { case fisi: sort(all(a), [&](T l, T r) { return l.f != r.f ? l.f < r.f : l.s < r.s; }); break; case fisd: sort(all(a), [&](T l, T r) { return l.f != r.f ? l.f < r.f : l.s > r.s; }); break; case fdsi: sort(all(a), [&](T l, T r) { return l.f != r.f ? l.f > r.f : l.s < r.s; }); break; case fdsd: sort(all(a), [&](T l, T r) { return l.f != r.f ? l.f > r.f : l.s > r.s; }); break; case sifi: sort(all(a), [&](T l, T r) { return l.s != r.s ? l.s < r.s : l.f < r.f; }); break; case sifd: sort(all(a), [&](T l, T r) { return l.s != r.s ? l.s < r.s : l.f > r.f; }); break; case sdfi: sort(all(a), [&](T l, T r) { return l.s != r.s ? l.s > r.s : l.f < r.f; }); break; case sdfd: sort(all(a), [&](T l, T r) { return l.s != r.s ? l.s > r.s : l.f > r.f; }); break; } }; template inline void rsort(vector &a) { sort(a.begin(), a.end(), greater()); }; template inline void rsort(vector &a, int len) { sort(a.begin(), a.begin() + len, greater()); }; template inline void rsort(vector &a, F f) { sort(a.begin(), a.end(), [&](U l, U r) { return f(l) > f(r); }); }; template inline void sortp(vector &a, vector &b) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); sort(c); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second;; } }; //F = T //例えばreturn p.fi + p.se; template inline void sortp(vector &a, vector &b, F f) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); sort(c, f); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void sortp(vector &a, vector &b, char type) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); sort(c, type); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void rsortp(vector &a, vector &b) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); rsort(c); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void rsortp(vector &a, vector &b, F f) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); rsort(c, f); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void sortt(vector &a, vector &b, vector &c) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); sort(r); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void sortt(vector &a, vector &b, vector &c, F f) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); sort(r, f); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void rsortt(vector &a, vector &b, vector &c, F f) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); rsort(r, f); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void sort2(vector> &a) { for (int i = 0, n = a.size(); i < n; i++)sort(a[i]); } template inline void rsort2(vector> &a) { for (int i = 0, n = a.size(); i < n; i++)rsort(a[i]); } template void fill(A (&a)[N], const T &v) { rep(i, N)a[i] = v; } template void fill(A (&a)[N][O], const T &v) { rep(i, N)rep(j, O)a[i][j] = v; } template void fill(A (&a)[N][O][P], const T &v) { rep(i, N)rep(j, O)rep(k, P)a[i][j][k] = v; } template void fill(A (&a)[N][O][P][Q], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)a[i][j][k][l] = v; } template void fill(A (&a)[N][O][P][Q][R], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)a[i][j][k][l][m] = v; } template void fill(A (&a)[N][O][P][Q][R][S], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)a[i][j][k][l][m][n] = v; } template void fill(V &xx, const T vall) { xx = vall; } template void fill(vector &vecc, const T vall) { for (auto &&vx: vecc) fill(vx, vall); } //@汎用便利関数 入力 template T _in() { T x; cin >> x; return (x); } #define _overloadin(_1, _2, _3, _4, name, ...) name #define in0() _in() #define in1(a) cin>>a #define in2(a, b) cin>>a>>b #define in3(a, b, c) cin>>a>>b>>c #define in4(a, b, c, d) cin>>a>>b>>c>>d #define in(...) _overloadin(__VA_ARGS__,in4,in3,in2 ,in1,in0)(__VA_ARGS__) #define _overloaddin(_1, _2, _3, _4, name, ...) name #define din1(a) int a;cin>>a #define din2(a, b) int a,b;cin>>a>>b #define din3(a, b, c) int a,b,c;cin>>a>>b>>c #define din4(a, b, c, d) int a,b,c,d;cin>>a>>b>>c>>d #define din(...) _overloadin(__VA_ARGS__,din4,din3,din2 ,din1)(__VA_ARGS__) #define _overloaddind(_1, _2, _3, _4, name, ...) name #define din1d(a) int a;cin>>a;a-- #define din2d(a, b) int a,b;cin>>a>>b;a--,b-- #define din3d(a, b, c) int a,b,c;cin>>a>>b>>c;a--,b--,c-- #define din4d(a, b, c, d) int a,b,c,d;cin>>a>>b>>c>>d;;a--,b--,c--,d-- #define dind(...) _overloaddind(__VA_ARGS__,din4d,din3d,din2d ,din1d)(__VA_ARGS__) #define _overloadout(_1, _2, _3, _4, name, ...) name #define out1(a) cout<(); } ll lin() { return _in(); } #define na(a, n) a.resize(n); rep(i,n) cin >> a[i]; #define nao(a, n) a.resize(n+1); rep(i,n) cin >> a[i+1]; #define nad(a, n) a.resize(n); rep(i,n){ cin >> a[i]; a[i]--;} #define na2(a, b, n) a.resize(n),b.resize(n);rep(i, n)cin >> a[i] >> b[i]; #define na2d(a, b, n) a.resize(n),b.resize(n);rep(i, n){cin >> a[i] >> b[i];a[i]--,b[i]--;} #define na3(a, b, c, n) a.resize(n),b.resize(n),c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i]; #define na3d(a, b, c, n) a.resize(n),b.resize(n),c.resize(n); rep(i, n){cin >> a[i] >> b[i] >> c[i];a[i]--,b[i]--,c[i]--;} #define nt(a, h, w) resize(a,h,w);rep(hi,h)rep(wi,w) cin >> a[hi][wi]; #define ntd(a, h, w) rs(a,h,w);rep(hi,h)rep(wi,w) cin >> a[hi][wi], a[hi][wi]--; #define ntp(a, h, w) fill(a,'#');rep(hi,1,h+1)rep(wi,1,w+1) cin >> a[hi][wi]; //デバッグ #define sp << " " << #define debugName(VariableName) # VariableName #define _deb1(x) cerr << debugName(x)<<" = "< sets() { vec res(trees); umap map; rep(i, n) map[root(i)].push_back(i); int i = 0; for (auto &&p:map) { int r = p.fi; res[i].push_back(r); for (auto &&v:p.se) { if (r == v)continue; res[i].push_back(v); } i++; } return res; } }; vb isPrime; vi primes; void setPrime() { int len = 4010101; isPrime.resize(4010101); fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= sqrt(len) + 5; ++i) { if (!isPrime[i])continue; for (int j = 2; i * j < len; ++j) { isPrime[i * j] = false; } } rep(i, len)if (isPrime[i])primes.pb(i); } //幾何 Pをcomplexとして扱う bool eq(double a, double b) { return fabs(a - b) < eps; } using C =complex; C rot(C &a, dou th) { return a * C(cos(th), sin(th)); } dou inpro(C &a, C &b) { return real(a * conj(b)); } //90度回転させて内積が0なら平行 bool line(C a, C b, C c) { C ab = b - a; C ac = c - a; //複素数の掛け算は回転 ab *= C(0, 1); return eq(inpro(ab, ac), 0); } bool line(P a, P b, P c) { return line(C(a.fi, a.se), C(b.fi, b.se), C(c.fi, c.se)); } bool line(int xa, int ya, int xb, int yb, int xc, int yc) { C a = C(xa, ya); C b = C(xb, yb); C c = C(xc, yc); return line(a, b, c); } //便利関数 //テスト用 char ranc() { return (char) ('a' + rand() % 26); } int rand(int min, int max) { assert(min <= max); if (min >= 0 && max >= 0) { return rand() % (max + 1 - min) + min; } else if (max < 0) { return -rand(-max, -min); } else { //+ if (rand() % 2) { return rand(0, max); //- } else { return -rand(0, -min); } } } vi ranv(int n, int min, int max) { vi v(n); rep(i, n)v[i] = rand(min, max); return v; } //単調増加 vi ranvi(int n, int min, int max) { vi v(n); bool bad = 1; while (bad) { bad = 0; v.resize(n); rep(i, n) { if (i && min > max - v[i - 1]) { bad = 1; break; } if (i)v[i] = v[i - 1] + rand(min, max - v[i - 1]); else v[i] = rand(min, max); } } return v; } void ranvlr(int n, int min, int max, vi &l, vi &r) { l.resize(n); r.resize(n); rep(i, n) { l[i] = rand(min, max); r[i] = l[i] + rand(0, max - l[i]); } } //便利 汎用 //strを整数として比較 string smax(str &a, str b) { if (sz(a) < sz(b)) { return b; } else if (sz(a) > sz(b)) { return a; } else { rep(i, sz(a)) { if (a[i] < b[i]) { return b; } else if (a[i] > b[i])return a; } } return a; } //strを整数として比較 string smin(str &a, str b) { if (sz(a) < sz(b)) { return a; } else if (sz(a) > sz(b)) { return b; } else { rep(i, sz(a)) { if (a[i] < b[i]) { return a; } else if (a[i] > b[i])return b; } } return a; } template int find(vector &a, const T key) { rep(i, sz(a))if (a[i] == key)return i; return -1; } template P find(vector> &a, const T key) { rep(i, sz(a)) rep(j, sz(a[0]))if (a[i][j] == key)return mp(i, j); return mp(-1, -1); } template T find(vector>> &a, const U key) { rep(i, sz(a))rep(j, sz(a[0]))rep(k, sz(a[0][0]))if (a[i][j][k] == key)return mt(i, j, k); return mt(-1, -1, -1); } template int count(V &a, const T k) { return a == k; } template int count(vector &a, const T k) { int ret = 0; fora(v, a)ret += count(v, k); return ret; } template int count_odd(V &a) { return a % 2; } template int count_odd(vector &a) { int ret = 0; fora(v, a)ret += count_odd(v); return ret; } template int count_even(V &a) { return a % 2 == 0; } template int count_even(vector &a) { int ret = 0; fora(v, a)ret += count_even(v); return ret; } //algorythm void iota(vector &ve, int s, int n) { ve.resize(n); iota(all(ve), s); } vi iota(int s, int n) { vi ve(n); iota(all(ve), s); return ve; } //便利 数学 int mod(int a, int m) { return (a % m + m) % m; } int pow(int a) { return a * a; }; ll fact(int v) { return v <= 1 ? 1 : v * fact(v - 1); } ll comi(int n, int r) { assert(n < 100); static vvi(pas, 100, 100); if (pas[0][0])return pas[n][r]; pas[0][0] = 1; rep(i, 1, 100) { pas[i][0] = 1; rep(j, 1, i + 1)pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j]; } return pas[n][r]; } void ole() { #ifdef _DEBUG debugline("ole"); exit(0); #endif string a = "a"; rep(i, 30)a += a; rep(i, 1 << 17)cout << a << endl; cout << "OLE 出力長制限超過" << endl; exit(0); } void tle() { while (inf)cout << inf << endl; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll gcd(vi b) { ll res = b[0]; for (auto &&v :b)res = gcd(v, res); return res; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } ll rev(ll a) { ll res = 0; while (a) { res *= 10; res += a % 10; a /= 10; } return res; } template vector rev(vector &a) { vector ret = a; reverse(all(ret)); return ret; } ll ceil(ll a, ll b) { if (b == 0) { debugline("ceil"); deb(a, b); ole(); return -1; } else return (a + b - 1) / b; } ll sqrt(ll a) { if (a < 0) { debugline("sqrt"); deb(a); ole(); } ll res = (ll) std::sqrt(a); while (res * res < a)res++; return res; } double log(double e, double x) { return log(x) / log(e); } ll sig(ll t) { return (1 + t) * t / 2; } ll sig(ll s, ll t) { return (s + t) * (t - s + 1) / 2; } vi divisors(int v) { vi res; for (int i = 1; i <= sqrt(v); ++i) { if (v % i == 0) { res.pb(i); if (i != v / i)res.pb(v / i); } } return res; } vi factorization(int v) { int tv = v; vi res; if (isPrime.size() == 0)setPrime(); for (auto &&p :primes) { if (v % p == 0)res.push_back(p); while (v % p == 0) { v /= p; } if (v == 1 || p * p > tv)break; } if (v > 1)res.pb(v); return res; } unordered_map factorizationMap(int v) { int tv = v; unordered_map res; if (isPrime.size() == 0)setPrime(); for (auto &&p :primes) { while (v % p == 0) { res[p]++; v /= p; } if (v == 1 || p * p > tv)break; } if (v > 1)res[v]++; return res; } int get(int a, int keta) { return (a / (int) pow(10, keta)) % 10; } int keta(int v) { int cou = 0; while (v) { cou++, v %= 10; } return cou; } int dsum(int v) { int ret = 0; for (; v; v /= 10)ret += v % 10; return ret; } int sumd(int v) { return dsum(v); } //変換系 template vector keys(vector> a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector keys(map a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector keys(umap a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector values(vector> a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } template vector values(map a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } template vector values(umap a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } vi list(int a) { vi res; while (a) { res.insert(res.begin(), a % 10); a /= 10; } return res; } template bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template bool chmax(const U &b) { return chmax(ma, b); } template bool chmin(T &a, const U &b) { if (b < a) { a = b; return true; } return false; } template bool chmin(const U &b) { return chmin(mi, b); } #define chmi chmin #define chma chmax template T min(T a, signed b) { return a < b ? a : b; } template T max(T a, signed b) { return a < b ? b : a; } template T min(T a, T b, T c) { return a >= b ? b >= c ? c : b : a >= c ? c : a; } template T max(T a, T b, T c) { return a <= b ? b <= c ? c : b : a <= c ? c : a; } template T min(vector a) { return *min_element(all(a)); } template T min(vector a, int n) { return *min_element(a.begin(), a.begin() + min(n, sz(a))); } template T min(vector a, int s, int n) { return *min_element(a.begin() + s, a.begin() + min(n, sz(a))); } template T max(vector a) { return *max_element(all(a)); } template T max(vector a, int n) { return *max_element(a.begin(), a.begin() + min(n, sz(a))); } template T max(vector a, int s, int n) { return *max_element(a.begin() + s, a.begin() + min(n, sz(a))); } template A max(A (&a)[N]) { A res = a[0]; rep(i, N)res = max(res, a[i]); return res; } template A max(A (&a)[N][O]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q], const T &v) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q][R]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q][R][S]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A min(A (&a)[N]) { A res = a[0]; rep(i, N)res = min(res, a[i]); return res; } template A min(A (&a)[N][O]) { A res = min(a[0]); rep(i, N)res = min(res, max(a[i])); return res; } template A min(A (&a)[N][O][P]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q], const T &v) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q][R]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q][R][S]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template T sum(vector v, int len = -1) { if (len == -1)len = v.size(); T res = 0; chmin(len, v.size()); rep(i, len)res += v[i]; return res; } template T sum(vector> &v, int h = -1, int w = -1) { if (h == -1)h = v.size(); if (w == -1)w = v[0].size(); T res = 0; chmin(h, v.size()); chmin(w, v[0].size()); rep(i, h)rep(j, w)res += v[i][j]; return res; } P sump(vp &v, int len = -1) { if (len == -1)len = v.size(); P res = {0, 0}; chmin(len, v.size()); rep(i, len) { res.fi += v[i].fi; res.se += v[i].se; } return res; } ///要素が0の時、返り値は0か1か template T mul(vector &v, int len = -1) { if (len == -1)len = v.size(); T res = 1; chmin(len, v.size()); rep(i, len)res *= v[i]; return res; } void clear(PQ &q) { while (q.size())q.pop(); } template void clear(queue &q) { while (q.size())q.pop(); } template T *negarr(int size) { T *body = (T *) malloc((size * 2 + 1) * sizeof(T)); return body + size; } template T *negarr2(int h, int w) { double **dummy1 = new double *[2 * h + 1]; double *dummy2 = new double[(2 * h + 1) * (2 * w + 1)]; dummy1[0] = dummy2 + w; for (int i = 1; i <= 2 * h + 1; i++) { dummy1[i] = dummy1[i - 1] + 2 * w + 1; } double **a = dummy1 + h; } //imoは0-indexed //ruiは1-indexed template vector imo(vector &v) { vector ret = v; rep(i, sz(ret) - 1)ret[i + 1] += ret[i]; return ret; } template vector imomi(vector &v) { vector ret = v; rep(i, sz(ret) - 1)chmin(ret[i + 1], ret[i]); return ret; } template struct ruiC { const vector rui; ruiC(vector &ru) : rui(ru) {} T operator()(int l, int r) { assert(l <= r); return rui[r] - rui[l]; } T operator[](int i) { return rui[i]; } }; template struct rruic { const T *rrui; rruic(T *ru) : rrui(ru) {} //n-1から-1へ T operator()(int l, int r) { assert(l >= r); return rrui[r] - rrui[l]; } T operator[](int i) { return rrui[i]; } }; template vector ruiv(vector &a) { vector ret(a.size() + 1); rep(i, a.size())ret[i + 1] = ret[i] + a[i]; return ret; } template ruiC ruic(vector &a) { vector ret = ruiv(a); return ruiC(ret); } template vector ruim(vector &a) { vector res(a.size() + 1, 1); rep(i, a.size())res[i + 1] = res[i] * a[i]; return res; } //template T *rrui(vector &a) { //右から左にかけての半開区間 (-1 n-1] template rruic rrui(vector &a) { int len = a.size(); T *body = (T *) malloc((len + 1) * sizeof(T)); T *res = body + 1; rer(i, len - 1)res[i - 1] = res[i] + a[i]; return rruic(res); } //掛け算 template T *rruim(vector &a) { int len = a.size(); T *body = (T *) malloc((len + 1) * sizeof(T)); T *res = body + 1; res[len - 1] = 1; rer(i, len - 1)res[i - 1] = res[i] * a[i]; return res; } template void inc(T &a, U v = 1) { a += v; } template void inc(vector &a, U v = 1) { for (auto &u :a)inc(u, v); } template void inc(vector &a) { for (auto &u :a)inc(u, 1); } template void plus(T &a, U v = 1) { a += v; } template void plus(vector &a, U v = 1) { for (auto &u :a)inc(u, v); } template void plus(vector &a) { for (auto &u :a)inc(u, 1); } template void dec(T &a, U v = 1) { a -= v; } template void dec(vector &a, U v = 1) { for (auto &u :a)dec(u, v); } template void dec(vector &a) { for (auto &u :a)dec(u, 1); } template void minu(T &a, U v = 1) { a -= v; } template void minu(vector &a, U v = 1) { for (auto &u :a)dec(u, v); } template void minu(vector &a) { for (auto &u :a)dec(u, 1); } inline bool inside(int h, int w, int H, int W) { return h >= 0 && w >= 0 && h < H && w < W; } inline bool inside(int v, int l, int r) { return l <= v && v < r; } #define ins inside ll u(ll a) { return a < 0 ? 0 : a; } template vector u(const vector &a) { vector ret = a; fora(v, ret)v = u(v); return ret; } #define MIN(a) numeric_limits::min() #define MAX(a) numeric_limits::max() ll goldd(ll left, ll right, function calc) { double GRATIO = 1.6180339887498948482045868343656; ll lm = left + (ll) ((right - left) / (GRATIO + 1.0)); ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); ll fl = calc(lm); ll fr = calc(rm); while (right - left > 10) { if (fl < fr) { right = rm; rm = lm; fr = fl; lm = left + (ll) ((right - left) / (GRATIO + 1.0)); fl = calc(lm); } else { left = lm; lm = rm; fl = fr; rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); fr = calc(rm); } } ll minScore = MAX(ll); ll resIndex = left; for (ll i = left; i < right + 1; i++) { ll score = calc(i); if (minScore > score) { minScore = score; resIndex = i; } } return resIndex; } ll goldt(ll left, ll right, function calc) { double GRATIO = 1.6180339887498948482045868343656; ll lm = left + (ll) ((right - left) / (GRATIO + 1.0)); ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); ll fl = calc(lm); ll fr = calc(rm); while (right - left > 10) { if (fl > fr) { right = rm; rm = lm; fr = fl; lm = left + (ll) ((right - left) / (GRATIO + 1.0)); fl = calc(lm); } else { left = lm; lm = rm; fl = fr; rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); fr = calc(rm); } } if (left > right) { ll l = left; left = right; right = l; } ll maxScore = MIN(ll); ll resIndex = left; for (ll i = left; i < right + 1; i++) { ll score = calc(i); if (maxScore < score) { maxScore = score; resIndex = i; } } return resIndex; } template T min(vector> &a) { T res = MAX(T); rep(i, a.size())chmin(res, *min_element(all(a[i]))); return res; } template T max(vector> &a) { T res = MIN(T); rep(i, a.size())chmax(res, *max_element(all(a[i]))); return res; } bool bget(ll m, int keta) { return (m >> keta) & 1; } int bget(ll m, int keta, int sinsuu) { m /= (ll) pow(sinsuu, keta); return m % sinsuu; } inline ll bit(int n) { return (1LL << (n)); } inline ll bit(int n, int sinsuu) { return (ll) pow(sinsuu, n); } //int bcou(ll m) { return __builtin_popcount(m & 0xFFFFFFFF) + __builtin_popcount(m >> 32); } #define bcou __builtin_popcountll //最下位ビット int lbit(int n) { return n & -n; } //最上位ビット int hbit(int n) { n |= (n >> 1); n |= (n >> 2); n |= (n >> 4); n |= (n >> 8); n |= (n >> 16); n |= (n >> 32); return n - (n >> 1); } //初期化は0を渡す ll nextComb(ll &mask, int n, int r) { if (!mask)return mask = (1LL << r) - 1; ll x = mask & -mask; //最下位の1 ll y = mask + x; //連続した下の1を繰り上がらせる ll res = ((mask & ~y) / x >> 1) | y; if (bget(res, n))return mask = 0; else return mask = res; } //n桁以下でビットがr個立っているもののvectorを返す vl bitCombList(int n, int r) { vl res; int m = 0; while (nextComb(m, n, r)) { res.pb(m); } return res; } //大文字小文字を区別する int altoiaZ(char c) { if ('A' <= c && c <= 'Z')return c - 'A'; return c - 'a' + 26; } char itoalaZ(int i) { if (i < 26)return 'A' + i; return 'a' + i - 26; } //aもAも0を返す 基本小文字 int altoi(char c) { if ('A' <= c && c <= 'Z')return c - 'A'; return c - 'a'; } char itoal(int i) { return 'a' + i; } int ctoi(char c) { return c - '0'; } char itoc(int i) { return i + '0'; } int vtoi(vi &v) { int res = 0; if (sz(v) > 18) { debugline("vtoi"); deb(sz(v)); ole(); } rep(i, sz(v)) { res *= 10; res += v[i]; } return res; } vi itov(int i) { vi res; while (i) { res.pb(i % 10); i /= 10; } rev(res); return res; } vector> ctoi(vector> s, char c) { int n = sz(s), m = sz(s[0]); vector> res(n, vector(m)); rep(i, n)rep(j, m)res[i][j] = s[i][j] == c; return res; } #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); void compress(vi &a) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); UNIQUE(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } } void compress(int a[], int len) { vi b; for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); UNIQUE(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } } //要素が見つからなかったときに困る #define binarySearch(a, v) (binary_search(all(a),v)) #define lowerIndex(a, v) (lower_bound(all(a),v)-a.begin()) #define lowerBound(a, v) (*lower_bound(all(a),v)) #define upperIndex(a, v) (upper_bound(all(a),v)-a.begin()) #define upperBound(a, v) (*upper_bound(all(a),v)) #define ans(a) cout< inline void fin(T s) { cout << s << endl, exit(0); } //機能拡張 vp vtop(vi &a, vi &b) { vp res(sz(a)); rep(i, sz(a))res[i] = mp(a[i], b[i]); return res; } void ptov(vp &p, vi &a, vi &b) { a.resize(sz(p)); b.resize(sz(p)); rep(i, sz(p))a[i] = p[i].fi, b[i] = p[i].se; } template basic_string<_CharT, _Traits, _Alloc> operator+(const basic_string<_CharT, _Traits, _Alloc> &__lhs, const int __rv) { basic_string<_CharT, _Traits, _Alloc> __str(__lhs); __str.append(to_string(__rv)); return __str; } template void operator+=(basic_string<_CharT, _Traits, _Alloc> &__lhs, const int __rv) { __lhs += to_string(__rv); } template basic_string<_CharT, _Traits, _Alloc> operator+(const basic_string<_CharT, _Traits, _Alloc> &__lhs, const signed __rv) { basic_string<_CharT, _Traits, _Alloc> __str(__lhs); __str.append(to_string(__rv)); return __str; } template void operator+=(basic_string<_CharT, _Traits, _Alloc> &__lhs, const signed __rv) { __lhs += to_string(__rv); } template void operator+=(queue &a, U v) { a.push(v); } template priority_queue, greater > &operator+=(priority_queue, greater > &a, U v) { a.push(v); return a; } template priority_queue &operator+=(priority_queue &a, U v) { a.push(v); return a; } template set &operator+=(set &a, U v) { a.insert(v); return a; } template set> &operator+=(set> &a, U v) { a.insert(v); return a; } template vector &operator+=(vector &a, U v) { a.pb(v); return a; } template vector operator+(const vector &a, U v) { vector ret = a; ret += v; return ret; } template vector operator+(U v, const vector &a) { vector ret = a; ret.insert(ret.begin(), v); return ret; } template vector &operator+=(vector &a, vector &b) { fora(v, b)a += v; return a; } template vector &operator+=(vector &a, initializer_list v) { for (auto &&va :v)a.pb(va); return a; } template vector &operator-=(vector &a, vector &b) { if (sz(a) != sz(b)) { debugline("vector operator-="); deb(a); deb(b); ole(); } rep(i, sz(a))a[i] -= b[i]; return a; } template vector operator-(vector &a, vector &b) { if (sz(a) != sz(b)) { debugline("vector operator-"); deb(a); deb(b); ole(); } vector res(sz(a)); rep(i, sz(a))res[i] = a[i] - b[i]; return res; } template void remove(vector &v, unsigned int i) { v.erase(v.begin() + i); } template void remove(vector &v, unsigned int s, unsigned int e) { v.erase(v.begin() + s, v.begin() + e); } template void removen(vector &v, unsigned int s, unsigned int n) { v.erase(v.begin() + s, v.begin() + s + n); } template void erase(vector &v, unsigned int i) { v.erase(v.begin() + i); } template void erase(vector &v, unsigned int s, unsigned int e) { v.erase(v.begin() + s, v.begin() + e); } template void erasen(vector &v, unsigned int s, unsigned int n) { v.erase(v.begin() + s, v.begin() + s + n); } template void insert(vector &v, unsigned int i, U t) { v.insert(v.begin() + i, t); } template void push_front(vector &v, U t) { v.insert(v.begin(), t); } template void insert(vector &v, unsigned int i, vector list) { for (auto &&va :list)v.insert(v.begin() + i++, va); } template void insert(vector &v, initializer_list list) { for (auto &&va :list)v.pb(va); } template void insert(vector &v, unsigned int i, initializer_list list) { for (auto &&va :list)v.insert(v.begin() + i++, va); } template void insert(set &v, vector list) { for (auto &&va :list)v.insert(va); } template void insert(set &v, initializer_list list) { for (auto &&va :list)v.insert(va); } vector split(const string a, const char deli) { string b = a + deli; int l = 0, r = 0, n = b.size(); vector res; rep(i, n) { if (b[i] == deli) { r = i; if (l < r)res.push_back(b.substr(l, r - l)); l = i + 1; } } return res; } vector split(const string a, const string deli) { string b = a + deli; int l = 0, r = 0, n = b.size(), dn = deli.size(); vector res; rep(i, n) { if (i + dn <= n && b.substr(i, i + dn) == deli) { r = i; if (l < r)res.push_back(b.substr(l, r - l)); i += dn - 1; l = i + 1; } } return res; } void yn(bool a) { if (a)cout << "yes" << endl; else cout << "no" << endl; } void Yn(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; } void YN(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; } void fyn(bool a) { if (a)cout << "yes" << endl; else cout << "no" << endl; exit(0); } void fYn(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; exit(0); } void fYN(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; exit(0); } void Possible(bool a) { if (a)cout << "Possible" << endl; else cout << "Impossible" << endl; exit(0); } int n, m, k, d, H, W, x, y, z, q; int cou; vi a, b, c; vvi (s, 0, 0); vvc (ba, 0, 0); vp p; template struct edge { int from, to; T cost; int id; int type; edge(int f, int t, T c = 1, int id = -1, int ty = -1) : from(f), to(t), cost(c), id(id), type(ty) {} bool operator<(const edge &b) const { return cost < b.cost; } bool operator>(const edge &b) const { return cost > b.cost; } }; template class graph { protected: vector _used; public : vector>> g; vector> edges; int n; graph(int n) : n(n) { g.resize(n), _used.resize(n); } void clear() { g.clear(), edges.clear(); } void resize(int n) { this->n = n; g.resize(n); _used.resize(n); } int size() { return g.size(); } vector > &operator[](int i) { return g[i]; } virtual void add(int from, int to, T cost, int id, int ty) = 0; virtual bool used(edge &e) = 0; virtual bool used(int id) = 0; virtual void del(edge &e) = 0; virtual void del(int id) = 0; }; template class digraph : public graph { public: using graph::g; using graph::n; using graph::edges; using graph::_used; digraph(int n) : graph(n) {} void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("digraph add"); deb(f, t, cost, id, ty); ole(); } if (id == -1)id = edges.size(); g[f].emplace_back(f, t, cost, id, ty); edges.emplace_back(f, t, cost, id, ty); } bool used(edge &e) { return _used[e.id]; } bool used(int id) { return _used[id]; } void del(edge &e) { _used[e.id] = _used[e.id ^ 1] = 1; } void del(int id) { _used[id] = _used[id ^ 1] = 1; } }; template class undigraph : public graph { public: using graph::g; using graph::n; using graph::edges; using graph::_used; undigraph(int n) : graph(n) { } void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("undigraph add"); deb(f, t, cost, id, ty); ole(); } if (id == -1)id = edges.size(); g[f].emplace_back(f, t, cost, id, ty); g[t].emplace_back(t, f, cost, id + 1, ty); edges.emplace_back(f, t, cost, id, ty); edges.emplace_back(t, f, cost, id + 1, ty); } void add(edge &e) { int f = e.from, t = e.to, ty = e.type; T cost = e.cost; add(f, t, cost, ty); } bool used(edge &e) { return _used[e.id]; } bool used(int id) { return _used[id]; } void del(edge &e) { _used[e.id] = _used[e.id ^ 1] = 1; } void del(int id) { _used[id] = _used[id ^ 1] = 1; } }; template vector dijkstra(const graph &g, int s, int cant_arrive = -1) { if (!(0 <= s && s < g.n)) { debugline("dijkstra"); deb(s, g.n); ole(); } T initValue = MAX(T); vector dis(g.n, initValue); priority_queue, vector>, greater>> q; dis[s] = 0; q.emplace(0, s); while (q.size()) { T nowc = q.top().fi; int i = q.top().se; q.pop(); if (dis[i] != nowc)continue; for (auto &&e : g.g[i]) { int to = e.to; T cost = nowc + e.cost; if (dis[to] > cost) { dis[to] = cost; q.emplace(dis[to], to); } } } //基本、たどり着かないなら-1 if (cant_arrive == -1)for (auto &&d :dis) if (d == initValue)d = -1; return dis; } template vector> warshall(const graph &g, int cant_arrive = -1) { int n = g.n; vector > dis(n, vector(n, linf)); fora(e, g.edges) chmin(dis[e.from][e.to], e.cost); rep(i, n)dis[i][i] = 0; rep(k, n)rep(i, n)rep(j, n)chmin(dis[i][j], dis[i][k] + dis[k][j]); //基本、たどり着かないなら-1 if (cant_arrive == -1)rep(i, n)rep(j, n) if (dis[i][j] == linf)dis[i][j] = -1; return dis; } template class tree : public undigraph { public: using undigraph::g; using undigraph::n; using undigraph::edges; using undigraph::_used; vi dep; vi disv; private: bool never = 1; int root = -1; vector> par; bool costallone; void dfs(int v, int p, int d) { dep[v] = d; par[0][v] = p; int lim = (*this)[v].size(); for (int i = 0; i < lim; i++) { int t = g[v][i].to; if (t == p)con; dfs(t, v, d + 1); } } void built() { never = 0; n = g.size(); par.assign(30, vi(n)); dep.resize(n); costallone = 1; fora(e, edges)if (e.cost != 1)costallone = 0; dfs(root, -1, 0); rep(k, par.size() - 1) { rep(i, n) { if (par[k][i] == -1)par[k + 1][i] = -1; else par[k + 1][i] = par[k][par[k][i]]; } } if (costallone)disv = dep; else disv = dijkstra(*this, root); } int _lca(int u, int v) { if (dep[u] > dep[v])swap(u, v); rep(k, par.size()) { if ((dep[u] - dep[v]) >> k & 1) { v = par[k][v]; } } if (u == v)return u; rer(k, par.size() - 1) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } return par[0][u]; } int _dis(int u, int v) { int p = _lca(u, v); return disv[u] + disv[v] - disv[p] * 2; } public: tree(int n, int root = 0) : undigraph(n), root(root) {} bool leaf(int v) { return sz(g[v]) == 1 && v != root; } int dis(int u, int v) { if (never) { built(); } return _dis(u, v); } int lca(int u, int v) { if (never) { built(); } return _lca(u, v); } }; //辺によりメモリを大量消費 // よってedgesを消している //頂点10^6でメモリを190MB(制限の8割)使う //軽量化のため、辺を持たないbig gridクラスがあってもいいかもしれない // template class grid_k6 : public undigraph { public: using undigraph::g; using undigraph::n; using undigraph::edges; using undigraph::_used; int H, W; int eid = 0; void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("grid_k6 add"); deb(f, t, cost, id, ty); ole(); } g[f].emplace_back(f, t, cost, eid++, ty); g[t].emplace_back(t, f, cost, eid++, ty); } int getid(int h, int w) { if (!inside(h, w, H, W))return -1; return W * h + w; } P get2(int id) { return mp(id / W, id % W); } P operator()(int id) { return get2(id); } int operator()(int h, int w) { return getid(h, w); } grid_k6(int H, int W) : H(H), W(W), undigraph(H * W) { rep(h, H) { rep(w, W) { int f = getid(h, w); if (w + 1 < W) add(f, getid(h, w + 1)); if (h + 1 < H)add(f, getid(h + 1, w)); } } } grid_k6(_vvc ba, char wall = '#') : H(sz(ba)), W(sz(ba[0])), undigraph(sz(ba) * sz(ba[0])) { rep(h, H) { rep(w, W) { if (ba[h][w] == wall)con; int f = getid(h, w); if (w + 1 < W && ba[h][w + 1] != wall) { add(f, getid(h, w + 1)); } if (h + 1 < H && ba[h + 1][w] != wall) { add(f, getid(h + 1, w)); } } } } void add(int fh, int fw, int th, int tw) { add(getid(fh, fw), getid(th, tw)); } }; //左上から右下に移動できる template class digrid_k6 : public digraph { public: using digraph::g; using digraph::n; using digraph::edges; using digraph::_used; int H, W; int eid = 0; void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("digrid_k6 add"); deb(f, t, cost, id, ty); ole(); } g[f].emplace_back(f, t, cost, eid++, ty); } int getid(int h, int w) { if (!inside(h, w, H, W))return -1; return W * h + w; } P get2(int id) { return mp(id / W, id % W); } P operator()(int id) { return get2(id); } int operator()(int h, int w) { return getid(h, w); } digrid_k6(int H, int W) : H(H), W(W), digraph(H * W) { rep(h, H) { rep(w, W) { int f = getid(h, w); if (w + 1 < W) add(f, getid(h, w + 1)); if (h + 1 < H)add(f, getid(h + 1, w)); } } } digrid_k6(_vvc ba, char wall = '#') : H(sz(ba)), W(sz(ba[0])), digraph(sz(ba) * sz(ba[0])) { rep(h, H) { rep(w, W) { if (ba[h][w] == wall)con; int f = getid(h, w); if (w + 1 < W && ba[h][w + 1] != wall) { add(f, getid(h, w + 1)); } if (h + 1 < H && ba[h + 1][w] != wall) { add(f, getid(h + 1, w)); } } } } void add(int fh, int fw, int th, int tw) { add(getid(fh, fw), getid(th, tw)); } }; template bool nibu(const graph &g) { if (g.edges.size() == 0)return true; UnionFind uf(g.n * 2); for (auto &&e :g.edges)uf.unite(e.from, e.to + g.n), uf.unite(e.from + g.n, e.to); rep(i, g.n)if (uf.same(i, i + g.n))return 0; return 1; } //二部グラフを色分けした際の頂点数を返す template vp nibug(graph &g) { vp cg; if (!nibu(g)) { debugline("nibu"); ole(); } int _n = g.size(); vb _was(_n); queue

q; rep(i, _n) { if (_was[i])continue; q.push(mp(i, 1)); _was[i] = 1; int red = 0; int coun = 0; while (q.size()) { int now = q.front().fi; int col = q.front().se; red += col; coun++; q.pop(); forg(gi, g[now]) { if (_was[t])continue; q.push(mp(t, col ^ 1)); _was[t] = 1; } } cg.push_back(mp(red, coun - red)); } return cg; } //閉路がなければtrue bool topo(vi &res, digraph &g) { int n = g.g.size(); vi nyu(n); rep(i, n)for (auto &&e :g[i])nyu[e.to]++; queue st; rep(i, n)if (nyu[i] == 0)st.push(i); while (st.size()) { int v = st.front(); st.pop(); res.pb(v); fora(e, g[v]) if (--nyu[e.to] == 0)st.push(e.to); } return res.size() == n; } //辞書順最小トポロジカルソート bool topos(vi &res, digraph &g) { int n = g.g.size(); vi nyu(n); rep(i, n)for (auto &&e :g[i])nyu[e.to]++; //小さい順 priority_queue, greater > q; rep(i, n)if (nyu[i] == 0)q.push(i); while (q.size()) { int i = q.top(); q.pop(); res.pb(i); fora(e, g[i])if (--nyu[e.to] == 0)q.push(e.to); } return res.size() == n; } void solve() { cin >> n; undigraph<> g(2 * k5); rep(i, n-1 ) { int f, t; cin >> f >> t; --f, --t; g.add(f, t); } rep(i,n){ cou+=u(sz(g[i])-2); } cout << cou << endl; } int my(int n, vi a) { return 0; } int sister(int n, vi a) { return 0; } signed main() { solve(); #define _arg n,a //cin>>n; //na(a,n); //my(_arg); //cout << my(_arg) << endl; #ifdef _DEBUG bool bad = 0; for (int i = 0, ok = 1; i < k5 && ok; i++) { int n = rand(1, 3); vi a = ranv(m, 1, 10); int myres = my(_arg); int res = sister(_arg); ok = myres == res; if (!ok) { cout << n << endl; cout << a << endl; cout << "正解 : " << res << endl; cout << "出力 : " << myres << endl; bad = 1; break; } } #endif return 0; };