/* * じょえチャンネル * 高評価・チャンネル登録よろしくおねがいします! * https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") //here!!! // define int long long !!!!! #define int long long // define int long long !!!!! //#define mod 1000000007ll constexpr int mod = 998244353ll; typedef long long ll; #ifdef int #define inf (int)(3e18) #else #define inf (int)(5e8) #endif #define intt long long #define itn long long #define innt long long #define P pair #define rep(i,n) for(int i=0;i=0;i--) #define REV_REP(i,n) for(int i=n;i>=1;i--) #define ALL(v) v.begin(),v.end() #define smallpriority_queue(T) priority_queue,greater> using namespace std; //Library //モッドパウ inline int modpow(int x, int y, int m = mod) { int res = 1; while (y) { if (y & 1) { res *= x; res %= m; } x = x * x % m; y /= 2; } return res; } int mypow(int x, int y) { int res = 1; while (y) { if (y % 2) { res *= x; } x = x * x; y /= 2; } return res; } //is the number (x) a prime number? bool prime(int x) { if (!x || x == 1) { return false; } for (int i = 2; i * i <= x; i++) { if (!(x % i)) { return false; } } return true; } //saidai-kouyakusuu inline int gcd(int x, int y) { if (!y) { return x; } return gcd(y, x % y); } //number of keta int keta(int x) { int ans = 0; while (x) { x /= 10; ans++; } return ans; } //number of 2shinsuu keta int bitketa(int x) { int ans = 0; while (x) { x >>= 1; ans++; } return ans; } //sum of keta int ketasum(int x) { int ans = 0; while (x) { ans += x % 10; x /= 10; } return ans; } inline int lcm(int x, int y) { int ans = x / gcd(x, y) * y; return ans; } int twobeki(int x) { int ans = 0; while (1) { if (!(x & 1)) { ans++; x >>= 1; } else { break; } } return ans; } template inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } void Yes(){ cout<<"Yes"< x)return 0; // cout< class SegTree { int n; vector node; T def; function operation; function update; public: SegTree(unsigned int _n, T _def, function _operation, function _update) : def(_def), operation(_operation), update(_update) { n=1; while (n < _n) { n *= 2; } node = vector(n * 2, def); } SegTree(vector& initvec, function _operation, function _update) : operation(_operation), update(_update) { n=1; while (n < initvec.size()) { n *= 2; } node = vector(n * 2, def); for(int i=n;i=1;i--){ node[i]=operation(node[i*2],node[i*2+1]); } } void change(int i,T x){ i+=n; node[i]=update(node[i],x); while (i>=1) { i>>=1; node[i]=operation(node[i*2],node[i*2+1]); } } T query(int l, int r){ l+=n; r+=n; T rx=def,lx=def; while(l>=1; r>>=1; } return operation(lx,rx); } T operator [] (const int& x){ return node[x+n]; } void fill(T x) { std::fill(ALL(node), x); } void print() { rep(i, n)std::cout << operator[](i) << " "; std::cout << std::endl; } }; #define R_MIN ([](long long a, long long b) { return min(a, b); }) #define R_MAX ([](long long a, long long b) { return max(a, b); }) #define R_SUM ([](long long a, long long b) { return a + b; }) #define NORMAL_UPDATE ([](long long a, long long b) { return b; }) #define ADD_UPDATE ([](long long a, long long b) { return a + b; }) #define MINUS_UPDATE ([](long long a, long long b) { return a - b; } class Union_Find { vector par; vector rankmy; vector ookisa; public: Union_Find(int size) { par = vector(size); rankmy = vector(size); ookisa=vector(size); for (int i = 0; i < size; i++) { par[i] = i; ookisa[i]=1; } } int find(int x) { if (par[x] == x) { return x; } return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) { return; } if (rankmy[x] < rankmy[y]) { par[x] = y; ookisa[y]+=ookisa[x]; ookisa[x]=0; } else { par[y] = x; ookisa[x]+=ookisa[y]; ookisa[y]=0; if (rankmy[x] == rankmy[y]) { rankmy[x]++; } } } int size(int i){ i=find(i); return ookisa[i]; } bool same(int x, int y){ return find(x) == find(y); } }; class BIT { vector data; int size=0; public: BIT(int _size){ data=vector(_size+1); size=_size; } void add(int i,int x){ while (i<=size) { data[i]+=x; i += i & -i; } } int sum(int i){ assert(i<=size); int s=0; while(i>0){ s+=data[i]; i -= i & -i; } return s; } int lower_bound(int x){ if(x<=0){ return 0; }else{ int i=0;int r=1; while(r0;len=len>>1) { if(i+lenx) { return 0; } if (x<0) { return 0; } return perm[x] * modpow(perm[x - y], mod - 2) % mod * modpow(perm[y], mod - 2) % mod; } struct Dot { double x; double y; Dot(double _x=0.0, double _y=0.0){ x=_x; y=_y; } }; struct Dot_i { int x; int y; Dot_i(int _x=0, int _y=0){ x=_x; y=_y; } }; double kyori(pair f, pair s) { double ans = 0; double t = fabs(f.first - s.first); double y = fabs(f.second - s.second); ans = sqrt(t * t + y * y); return ans; } double kyori(Dot f, Dot s) { double ans = 0; double t = fabs(f.x - s.x); double y = fabs(f.y - s.y); ans = sqrt(t * t + y * y); return ans; } inline string stringmax(string& x,string& y){ if (x.size()>y.size()) { return x; } if (x.size()y[i]) { return x; } if (x[i] RollingHash(string &s, string& t){ // vector ans; // __int128 h=0,hamod=0,ki=0,kim=0,hikaku=0,one=0; // one=1; // ki=1000000007ll; // hamod=(one<<61)-1; // kim=1; // rep(i,t.size()){ // hikaku*=ki; // h*=ki; // kim*=ki; // hikaku+=t[i]; // h+=s[i]; // hikaku%=hamod; // h%=hamod; // kim%=hamod; // } // rep(i,(int)s.size()-(int)t.size()+1){ // if (h==hikaku) { // ans.emplace_back(i); // } // h*=ki; // h%=hamod; // h+=s[i+(int)t.size()]; // h%=hamod; // h+=hamod; // h-=s[i]*kim%hamod; // h%=hamod; // } // return ans; //} struct edge { int to; int length; edge(int _to, int _length){ to=_to; length=_length; } }; vector djkstra(vector> &road,int start){ vector kyo(road.size(),inf); smallpriority_queue(P) q; q.push({0,start}); kyo[start]=0; while (q.size()) { int x=q.top().second; itn now=q.top().first; q.pop(); if (kyo[x]now+i.length) { kyo[i.to]=now+i.length; q.push({kyo[i.to],i.to}); } } } return kyo; } template void change_to_unique(vector &v){ std::sort(ALL(v)); auto k=unique(ALL(v)); if(k!=v.end())v.erase(k,v.end()); } double kodo_dosuu(double r){ return 180.0*r/(double)M_PI; } double dosuu_kodo(double r){ return r*(double)M_PI/180.0; } double kakudo(Dot a,Dot b1,Dot b2){ double size1=kyori(a,b1),size2=kyori(a,b2); double nai=(b1.x-a.x)*(b2.x-a.x)+(b1.y-a.y)*(b2.y-a.y); nai/=size1*size2; return kodo_dosuu(acos(nai)); } class Tree { // 1-indexed // size up to 2^20(10^6) vector> road; vector depthdata; vector par[20]; int root; int big; public: void dfs(int x, int p){ for(auto&i:road[x]){ if (i==p) { continue; } depthdata[i]=depthdata[x]+1; par[0][i]=x; dfs(i,x); } } int n_par(int x, int n){ rep(i,20){ if (n&(1ll<depthdata[y]) { swap(x,y); } y=n_par(y, depthdata[y]-depthdata[x]); if (x==y) { return x; } for(int i=19;i>=0;i--){ if (par[i][x]!=par[i][y]) { x=par[i][x]; y=par[i][y]; } } return par[0][x]; } int depth(int x){ assert(x<=big); return depthdata[x]; } int size(){ return big; } int distance(int x, int y){ return depthdata[x]+depthdata[y]-depthdata[lca(x, y)]*2; } Tree(vector> road, int _root=1):road(road){ root=_root; big=(int)road.size()-1; depthdata.resize(road.size()); rep(i,20){ par[i].resize(road.size()); } dfs(root,root); rep(i,19){ REP(j,big){ par[i+1][j]=par[i][par[i][j]]; } } } Tree(vector *_road,int _size, int _root=1){ root=_root; big=_size; road.resize(big+1); REP(i,big){ road[i]=_road[i]; } depthdata.resize(big+1); rep(i,20){ par[i].resize(big+1); } dfs(root,root); rep(i,19){ REP(j,big){ par[i+1][j]=par[i][par[i][j]]; } } } }; #define endl "\n" //interactive の時に注意!!! #define Endl "\n" //interactive の時に注意!!! #define cinn cin #define printd cout<=f;i--) #define hen_rep(i,l,step) for(int i=0;i road[100004]; signed main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cin>>a>>b; cout<