/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=99824LL;
vector<ll> fat,ifat;
ll Mo_bucket; //sqrt(arr.size())
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
struct hash_pair
{
template <class T1, class T2>
size_t operator() (pair<T1, T2> p) const
{
size_t hash1 = hash<T1>()(p.first);
size_t hash2 = hash<T2>()(p.second);
return (hash1 ^ hash2);
}
};
template <class A, class B, class C>
pair<A,B> operator *(pair<A,B> a, C c) {a.ff*=c; a.ss*=c; return a;}
template<class A,class B>
pair<A,B> operator + (pair<A,B> a, pair<A,B> b) {return mp(a.ff+b.ff,a.ss+b.ss);}
template<class A,class B>
pair<A,B> operator - (pair<A,B> a, pair<A,B> b) {return mp(a.ff-b.ff,a.ss-b.ss);}
template<class T=ll>
bool cmp(T A, T B) {return (A<B);}
template<class T=double>
bool eq(T a, T b) {return(abs(a-b)<EPS);}
class complex
{
public:
double re; double im;
complex() {re=0.0; im=0.0;}
complex(double r, double i) {re=r; im=i;}
complex(double r) {re=r; im=0.0;}
complex operator !() //conjugate
{
complex ans(re,-im); return ans;
}
complex operator + (complex z) {complex ans(re+z.re,im+z.im); return ans;}
complex operator - (complex z) {complex ans(re-z.re,im-z.im); return ans;}
void operator += (complex z) {re+=z.re; im+=z.im;}
void operator -= (complex z) {re-=z.re; im-=z.im;}
complex operator * (complex z) {complex ans(re*z.re-im*z.im,re*z.im+z.re*im); return ans;}
void operator *= (complex z) {complex ans=(*this)*z; *this=ans;}
double norm() {double ans = sqrt(re*re+im*im); return ans;}
complex operator / (complex z) {double n = z.norm(); n=n*n; complex ans=!z; ans.re/=n; ans.im/=n; ans*=(*this); return ans;}
void operator /= (complex z) {complex ans=(*this)/z; *this=ans;}
bool operator == (complex z) {if(eq(re,z.re) && eq(im,z.im)) {return true;} else {return false;}}
bool operator < (complex z) {if(re<z.re) {return true;} else if(eq(re,z.re)) {return (im<z.im);} else {return false;}}
bool operator <= (complex z) {return (((*this)<z) || ((*this)==z));}
bool operator > (complex z) {return (z<(*this));}
bool operator >= (complex z) {return (z<=(*this));}
double arg()
{
if(re==0 && im>=0) {return (pi/2.0);}
if(re==0 && im<0) {return (3.0*pi/2.0);}
double val = im/re;
double ans = atan(val);
if(re<0) {ans=pi+ans;}
else if(im<0) {ans=2.0*pi+ans;}
return ans;
}
};
struct hash_complex
{
size_t operator() (complex z) const
{
return (2*sizeof(double));
}
};
complex polar(double len, double angle) //angle in radians
{
complex ans(cos(angle),sin(angle)); ans*=((complex) len);
return ans;
}
class segment
{
public:
complex a,b; //open in a, closed in b
segment() {a=0; b=0;}
segment(complex x) {a=0; b=x;}
segment(complex x, complex y) {a=x; b=y;}
bool belong(complex z)
{
if(z==a) {return false;}
if(z==b) {return true;}
complex w = (b-a)/(b-z);
if(!eq(w.im,0.0)) {return false;}
if(w.re>1.0) {return true;}
else {return false;}
}
};
class line
{
public:
complex a,b; //sometimes directed line a->b
line() {a=0; b=0;}
line(complex x, complex y) {a=x; b=y;}
line(segment s) {a=s.a; b=s.b;}
bool belong(complex z)
{
if(z==a || z==b) {return true;}
complex w = (b-a)/(b-z);
if(!eq(w.im,0.0)) {return false;}
else {return true;}
}
ld slope()
{
ld ans;
if(a.re!=b.re) {ans= (a.im-b.im)/(a.re-b.re);}
else {ans=(ld) INF;}
return ans;
}
};
bool parallel(line l, line r)
{
complex z1=l.a-l.b; complex z2=r.a-r.b;
complex z = z1/z2;
if(eq(z.im,0.0)) {return true;}
else {return false;}
}
complex intersection(line l, line r)
{
complex z1,z2,z3,z;
z1=(l.a-l.b)*((r.a*(!r.b))-(r.b*(!r.a)));
z2=(r.a-r.b)*((l.a*(!l.b))-(l.b*(!l.a)));
z3=((l.a-l.b)*(!r.a-!r.b))-((r.a-r.b)*(!l.a-!l.b));
z=(z2-z1)/z3;
return z;
}
bool intersect(line l, segment s)
{
line r(s);
complex z = intersection(l,r);
return s.belong(z);
}
bool intersect(segment s, segment t)
{
line l(s); line r(t);
return (intersect(l,t) && intersect(r,s));
}
bool concurrent(line l1,line l2, line l3)
{
complex z1 = intersection(l1,l2);
complex z2 = intersection(l2,l3);
complex z3 = intersection(l3,l1);
if(z1==z2 && z2==z3) {return true;}
else {return false;}
}
complex reflection(complex z, line l)
{
return ((((l.a-l.b)*(!z))+((!l.a)*l.b)-(l.a*(!l.b)))/((!l.a)-(!l.b)));
}
complex projection(complex z, line l)
{
return ((complex) (0.5)*(z+reflection(z,l)));
}
bool prependicular(line l, line r)
{
complex z = ((l.a-l.b)/(r.a-r.b));
if(eq(z.re,0.0)) {return true;}
else {return false;}
}
double distance(complex z, line l)
{
complex r = reflection(z,l);
complex ans=z-r;
return ans.norm();
}
class Triangle
{
public:
complex a, b, c;
complex *circumcentre_ptr;
Triangle() {a=0.0; b=0.0; c=0.0; circumcentre_ptr=nullptr;}
Triangle(complex x,complex y,complex z) {a=x; b=y; c=z; circumcentre_ptr=nullptr;}
Triangle operator !()
{
Triangle ANS(!a,!b,!c); return ANS;
}
double Area() //!!SIGNED AREA, is positive if, given point in interior, vertexes of triangle are in counterclockwise order.
{
complex ans;
complex z; z.im=0.25;
complex z1 = a*((!b)-(!c));
complex z2 = b*((!c)-(!a));
complex z3 = c*((!a)-(!b));
ans = z*(z1+z2+z3);
return ans.re;
}
complex centroid ()
{
complex z;
z.re=1.0/3.0;
return (z*(a+b+c));
}
complex circumcentre()
{
if(circumcentre_ptr!=nullptr) {return *circumcentre_ptr;}
complex *ans=new complex();
complex c1,c2,c3,z1,z2;
c1=a*(!a)*(b-c);
c2=b*(!b)*(c-a);
c3=c*(!c)*(a-b);
z1=c1+c2+c3;
c1=(!a)*(b-c);
c2=(!b)*(c-a);
c3=(!c)*(a-b);
z2=c1+c2+c3;
*ans=z1/z2;
circumcentre_ptr=ans;
return (*ans);
}
complex orthocentre()
{
complex h = a+b+c-(complex) 2.0*circumcentre();
return h;
}
};
bool similar(Triangle S, Triangle T) //ATTENTION: Directly similar. For reversely similar, try !S,T
{
complex z1,z2,z3;
z1=S.a*(T.b-T.c);
z2=S.b*(T.c-T.a);
z3=S.c*(T.a-T.b);
complex ans = z1+z2+z3;
if(ans==(complex) 0.0) {return true;}
else {return false;}
}
class Quadrilateral
{
public:
complex a,b,c,d;
Quadrilateral() {a=0; b=0; c=0; d=0;}
Quadrilateral(complex x, complex y, complex w, complex z) {a=x; b=y; c=w; d=z;}
bool concyclic()
{
complex z = ((b-a)*(c-d))/((c-a)*(b-d));
if(z.im==0.0) {return true;}
else {return false;}
}
double Area()
{
Triangle T1(a,b,c); Triangle T2(a,c,d);
return (T1.Area()+T2.Area());
}
complex MiquelPoint()
{
complex ans = ((a*c)-(b*d))/(a+c-b-d);
return ans;
}
};
class Polygon
{
public:
ll N;
vector<complex> v;
double *area_ptr;
bool *cyclic_ptr;
Polygon() {N=0LL; area_ptr=nullptr; cyclic_ptr=nullptr;}
Polygon(vector<complex> vertex) {v=vertex; N=v.size(); area_ptr=nullptr; cyclic_ptr=nullptr;}
double Area()
{
if(area_ptr!=nullptr) {return *area_ptr;}
double *ans = new double();
(*ans)=0.0;
REP(i,1,v.size()-1)
{
Triangle T(v[0],v[i],v[i+1]);
(*ans)+=T.Area();
}
area_ptr=ans;
return abs(*ans);
}
bool concylic()
{
if(cyclic_ptr!=nullptr) {return *cyclic_ptr;}
bool ans;
REP(i,3,v.size())
{
Quadrilateral Q(v[0],v[1],v[2],v[i]);
if(!Q.concyclic()) {ans=false;cyclic_ptr=&ans; return false;}
}
ans=true;
cyclic_ptr=&ans;
return true;
}
bool inside(complex z)
{
segment l(z,z+(complex) (INF));
ll intersections=0LL;
REP(i,0,N)
{
segment s(v[i],v[(i+1)%N]);
if(intersect(l,s)) {intersections++;}
}
if(intersections%2==0) {return false;}
else {return true;}
}
};
vector<ll> SweepSort(line l, vector<complex> v) //ans[i]=j means, in the sweep sorted point array, position i is v[j]
{
vector<pl> s;
REP(i,0,v.size())
{
Triangle T(v[i],l.b,l.a);
s.pb(mp(T.Area(),i));
}
sort(whole(s));
vector<ll> ans; REP(i,0,v.size()) {ans.pb(s[i].ss);}
return ans;
}
vector<ll> ArgSort(vector<complex> v, complex centre) //angles related to horizontal directed line through centre, angles from 0 to 360. ans[i]=j means, in the sweep sorted point array, position i is v[j]
{
vector<pl> angles; vector<ll> ans;
REP(i,0,v.size()) {complex z = v[i]-centre; angles.pb(mp(z.arg(),i));}
sort(whole(angles));
REP(i,0,v.size()) {ans.pb(angles[i].ss);}
return ans;
}
bool cmp_com(complex a, complex b) {return (a<b);}
bool cmp_pcomll(pair<complex,ll> a, pair<complex,ll> b) {if(a.ff<b.ff) {return true;} else if(a.ff>b.ff) {return false;} else {return (a.ss<b.ss);}}
pl ClosestPair(vector<complex> v) //returns (ind1,ind2) pair of indexes, ind1<ind2
{
ll N = v.size();
vector<complex> z = v; sort(whole(z),cmp_com);
pair<complex,complex> ans;
ld mind=(ld) INF;
set<pair<double,double> > s; s.insert(mp(z[0].im,z[0].re));
ll ind=0LL;
set<pair<double,double> >::iterator it;
REP(i,1,N)
{
while(z[i].re-z[ind].re>mind)
{
s.erase(mp(z[ind].im,z[ind].re));
ind++;
}
it=s.lower_bound(mp(z[i].im-mind,-INF));
while(it!=s.end() && it->ff<=z[i].im+mind)
{
complex x(it->ss,it->ff);
complex y = z[i]-x;
if(y.norm()<mind) {mind=y.norm(); ans.ff=x; ans.ss=z[i];}
it++;
}
s.insert(mp(z[i].im,z[i].re));
}
pl f_ans;
REP(i,0,N)
{
if(v[i]==ans.ff) {f_ans.ff=i;}
if(v[i]==ans.ss) {f_ans.ss=i;}
}
if(f_ans.ff>f_ans.ss) {swap(f_ans.ff,f_ans.ss);}
return f_ans;
}
vector<ll> ConvexHull(vector<complex> v, bool sorted=false) //returns vector of indexes of the convex hull
{
ll N=v.size();
vector<pair<complex,ll> > z; REP(i,0,N) {z.pb(mp(v[i],i));}
if(!sorted) {sort(whole(z),cmp_pcomll);}
vector<ll> ans,f_ans;
REP(i,0,N)
{
ans.pb(i);
if(i==0) {continue;}
while(ans.size()>2)
{
line l1(z[ans[ans.size()-3]].ff,z[ans[ans.size()-2]].ff);
line l2(z[ans[ans.size()-2]].ff,z[i].ff);
if(l1.slope()<l2.slope())
{
ans.erase(ans.end()-2);
}
else
{
break;
}
}
}
REP(i,0,ans.size()) {f_ans.pb(z[ans[i]].ss);}
ans.clear();
REP(i,0,N)
{
ans.pb(i);
if(i==0) {continue;}
while(ans.size()>2)
{
line l1(z[ans[ans.size()-3]].ff,z[ans[ans.size()-2]].ff);
line l2(z[ans[ans.size()-2]].ff,z[i].ff);
if(l1.slope()>l2.slope())
{
ans.erase(ans.end()-2);
}
else
{
break;
}
}
}
REP(i,1,ans.size()-1) {f_ans.pb(z[ans[i]].ss);}
sort(whole(f_ans));
return f_ans;
}
ll gcd(ll a,ll b)
{
if(a>b) {swap(a,b);}
if(a==0) {return b;}
else {return gcd(a,b%a);}
}
pl ExtEuclid(ll a, ll b) //return pair x,y: ax+by=(a,b)
{
if(a==0) {return mp(0LL,1LL);}
if(b==0) {return mp(1LL,0LL);}
bool swapped=false;
if(a<b) {swap(a,b); swapped=true;}
ll red=a%b; if(red<0) {red+=b;}
ll k=(a-red)/b;
pl nxt=ExtEuclid(red,b);
pl ans; ans.ff=nxt.ff; ans.ss=nxt.ss-k*nxt.ff;
if(swapped) {swap(ans.ff,ans.ss);}
return ans;
}
bool IsPrime(ll s)
{
if(s==1LL) {return false;}
if(s==2LL) {return true;}
REP(i,2LL,sqrt(s)+1LL)
{
if(s%i==0LL) {return false;}
}
return true;
}
vector<pl> PF(ll s)
{
vector<pl> pf;
if(s==2LL) {pf.pb(mp(2LL,1LL)); return pf;}
ll d=2LL;
while(d<=sqrt(s)+1LL)
{
if(s%d==0LL)
{
ll exp=0LL;
while(s%d==0LL)
{
exp++; s/=d;
}
pf.pb(mp(d,exp));
}
d++;
}
if(s>1LL)
{
pf.pb(mp(s,1LL));
}
return pf;
}
vector<ll> Sieve(ll N) //O(NloglogN)
{
vector<bool> valid; REP(i,0,N+1) {valid.pb(true);}
vector<ll> primes;
REP(i,2,N+1)
{
if(!valid[i]) {continue;}
ll cur=i; primes.pb(cur);
while(cur<=N) {valid[cur]=false; cur+=i;}
}
return primes;
}
ll phi(ll x)
{
ll n=x;
vector<pl> pri=PF(x);
ll ans=1;
REP(i,0,pri.size())
{
ans*=(ll) ((pow(pri[i].ff,pri[i].ss-(ld) 1)));
ans*=(pri[i].ff-1);
}
return ans;
}
ll ord(ll a, ll m)
{
ll cur=a; ll ans=1;
while((cur-1LL)%m!=0LL)
{
cur*=a; ans++; cur%=m;
}
return ans;
}
ll fastexp(ll a,ll e)
{
if(e==0) {return 1LL;}
if(e%2LL==0)
{
ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod;
}
else
{
ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod;
}
}
ll fastexp(ll a, ll e, ll m)
{
if(e==0) {return 1LL;}
if(e%2LL==0)
{
ll v=fastexp(a,(ll) e/2LL, m); return (v*v)%m;
}
else
{
ll v=fastexp(a,(ll) e/2LL, m); return (((v*v)%m)*a)%m;
}
}
ll fac(ll n, ll m)
{
ll ans=1LL; REP(i,1LL,n+1LL) {ans*=i; ans%=m;}
if(ans<0) {ans+=m;}
return ans;
}
ll inv(ll s)
{
return fastexp(s,mod-2LL);
}
ll inv(ll s, ll m)
{
return fastexp(s,phi(m)-1LL,m);
}
ll bin(ll n, ll k) //binomial coefficient
{
if(k<0LL || k>n) {return 0LL;}
ll ans=(((ifat[k]*ifat[n-k])%mod)*fat[n])%mod;
return ans;
}
ll bin(ll n, ll k, ll m)
{
if(k<0LL || k>n) {return 0LL;}
ll ans=fac(n,m);
ans*=inv(fac(k,m),m); ans%=m; ans*=inv(fac(n-k,m),m); ans%=m;
if(ans<0) {ans+=m;}
return ans;
}
void Calcfat(ll n)
{
ll ans=1LL; fat.pb(ans);
REP(i,1LL,n+1LL) {ans*=i; ans%=mod; fat.pb(ans);}
REP(i,0,n+1) {ifat.pb(inv(fat[i]));}
}
ll CRT(vector<pl> a) //a[i].ff=ai, a[i].ss=mi
{
REP(i,0,a.size()) {a[i].ff%=a[i].ss;}
ll ans=0LL; vector<ll> X; ll p=1LL; REP(i,0,a.size()) {p*=a[i].ss;}
REP(i,0,a.size()) {X.pb(p/a[i].ss);}
ll val;
REP(i,0,a.size())
{
val=a[i].ff*X[i]*inv(X[i],a[i].ss); val%=p; ans+=val; ans%=p;
}
if(ans<0) {ans+=p;}
return ans;
}
class ModInt
{
public:
ll a; ll m;
ModInt() {a=0LL; m=mod;}
ModInt(ll val) {a=val; m=mod; a%=m; a+=m; a%=m;}
ModInt operator + (ModInt b) {ModInt ans(a+b.a); return ans;}
ModInt operator - (ModInt b) {ModInt ans(a-b.a); return ans;}
ModInt operator * (ModInt b) {ModInt ans(a*b.a); return ans;}
ModInt operator / (ModInt b) {ModInt ans(a*inv(b.a)); return ans;}
void operator ++() {a++; a%=m; a+=m; a%=m;}
void operator --() {a--; a%=m; a+=m; a%=m;}
void operator +=(ModInt b) {ModInt ans=(*(this)) + b; a=ans.a;}
void operator -=(ModInt b) {ModInt ans=(*(this)) - b; a=ans.a;}
void operator *=(ModInt b) {ModInt ans=(*(this))*b; a=ans.a;}
void operator /=(ModInt b) {ModInt ans=(*(this))/b; a=ans.a;}
bool operator ==(ModInt b) {if((a-b.a)%m==0) {return true;} else {return false;}}
};
ostream & operator << (ostream &out, ModInt &M) {cout<<M.a; return out;}
istream & operator >> (istream &in, ModInt &M) {ll a; cin>>a; ModInt ans(a); M=a; return in;}
class Matrix
{
public:
ll N,M;
vector<vector<double> > a;
ll rank;
Matrix *Red, *Inv, *Trans; double det;
vector<bool> pivot;
Matrix() {N=0LL; M=0LL; Red=nullptr; Inv=nullptr; Trans=nullptr;}
Matrix (vector<vector<double> > x)
{
N=x.size(); M=x[0].size(); a=x; rank=0LL; REP(i,0,M) {pivot.pb(false);}
Red=nullptr; Inv=nullptr; Trans=nullptr;
}
Matrix operator + (Matrix B) //O(NM)
{
if((*this).N!=B.N || (*this).M!=B.M) {Matrix ANS; return ANS;}
vector<vector<double> > ans; vector<double> xx; REP(i,0,(*this).M) {xx.pb(0.0);} REP(i,0,(*this).N) {ans.pb(xx);}
REP(i,0,(*this).N) {REP(j,0,(*this).M) {ans[i][j]=(*this).a[i][j]+B.a[i][j];}}
Matrix ANS(ans); return ANS;
}
Matrix operator * (Matrix B) //O(N^3)
{
if(M!=B.N) {Matrix ANS; return ANS;}
vector<vector<double> > d; vector<double> xx; REP(i,0,B.M) {xx.pb(0.0);} REP(i,0,N) {d.pb(xx);}
REP(i,0,N)
{
REP(j,0,B.M)
{
double sum=0.0; REP(z,0,M) {sum+=(a[i][z]*B.a[z][j]);}
d[i][j]=sum;
}
}
Matrix ANS(d);
return ANS;
}
Matrix operator * (double c) //O(NM)
{
Matrix ANS = (*this); REP(i,0,N) {REP(j,0,M) {ANS.a[i][j]*=c;}}
return ANS;
}
Matrix operator - (Matrix B)
{
return ((*this)+B*(-1.0));
}
bool operator ==(Matrix B)
{
return ((*this).a==B.a);
}
bool operator !=(Matrix B)
{
if((*this)==B) {return false;}
else {return true;}
}
void operator +=(Matrix B) {*this=(*this)+B;}
void operator -=(Matrix B) {*this=(*this)-B;}
void operator *=(Matrix B) {*this=(*this)*B;}
void operator *=(double c) {*this=(*this)*c;}
void operator /=(double c) {*this=(*this)*(1.0/c);}
void operator /=(Matrix B) {B.RRE(); *this=(*this)*(*(B.Inv));}
Matrix operator ~()
{
if(Trans!=nullptr) {return *Trans;}
vector<double> xx; REP(i,0,N) {xx.pb(0.0);}
vector<vector<double> > ans; REP(i,0,M) {ans.pb(xx);}
REP(i,0,M) {REP(j,0,N) {ans[i][j]=a[j][i];}}
Matrix *RESULT = new Matrix(ans); Trans=RESULT;
return *RESULT;
}
void disp()
{
REP(i,0,N) {REP(j,0,M) {cout<<a[i][j]<<" ";} cout<<endl;}
}
void Inp()
{
ll NN,MM; cin>>NN>>MM; N=NN; M=MM;
vector<double> xx; REP(i,0,M) {xx.pb(0.0);} REP(i,0,N) {a.pb(xx);}
double c; REP(i,0,N) {REP(j,0,M) {cin>>c; a[i][j]=c;}}
REP(i,0,M) {pivot.pb(false);}
}
Matrix RRE() //Reduced Row Echelon Form, O(N*M^2), also builds "inverse" matrix up
{
if(Red!=nullptr) {return *Red;}
det=1.0;
rank=0LL;
Matrix *A= new Matrix(); *A=*this;
Matrix *Inverse = new Matrix();
vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {(*Inverse).a.pb(xx);}
(*Inverse).N=N; (*Inverse).M=N; REP(i,0,N) {(*Inverse).a[i][i]=1.0;}
vector<bool> v; REP(i,0,N) {v.pb(true);}
REP(ind,0,M)
{
ll line=0LL;
while(line<N)
{
if(!v[line]) {line++; continue;}
if((*A).a[line][ind]!=0.0) {break;}
line++;
}
if(line==N) {continue;}
pivot[ind]=true;
double c=(*A).a[line][ind]; det*=c;
REP(i,0,M) {(*A).a[line][i]/=c;}
REP(i,0,N) {(*Inverse).a[line][i]/=c;}
v[line]=false; rank++;
REP(i,0,N)
{
if(i==line) {continue;}
double c=(*A).a[i][ind];
if(c==0.0) {continue;}
REP(j,0,M) {(*A).a[i][j]-=((*A).a[line][j]*c);}
REP(j,0,N) {(*Inverse).a[i][j]-=((*Inverse).a[line][j]*c);}
}
}
vector<pair<pair<vector<double> ,vector<double> >, ll > > ToOrder; REP(i,0,N) {ToOrder.pb(mp(mp((*A).a[i],(*Inverse).a[i]),i));}
sort(ToOrder.begin(),ToOrder.end());
reverse(ToOrder.begin(),ToOrder.end());
(*A).a.clear(); REP(i,0,N) {(*A).a.pb(ToOrder[i].ff.ff);}
(*Inverse).a.clear(); REP(i,0,N) {(*Inverse).a.pb(ToOrder[i].ff.ss);}
Red=A; Inv=Inverse;
if(rank!=N || rank!=M) {det=(double) 0.0;}
ll inversions=0LL;
REP(i,0,N) {REP(j,i+1,M) {if(ToOrder[i].ss>ToOrder[j].ss) {inversions++;}}}
if(inversions%2!=0) {det*=(-1.0);}
return *Red;
}
vector<double> Gauss(vector<double> b) //gives one possible solution if there is one to Ax=b in O(N^2)
{
Matrix A=RRE(); Matrix B=*Inv;
vector<double> ans; REP(i,0,M) {ans.pb(0.0);}
double val; ll piv=0LL;
REP(i,0,N)
{
val=0.0; REP(j,0,N) {val+=B.a[i][j]*b[j];}
while(!pivot[piv] && piv<M) {piv++;}
if(piv<M) {ans[piv]=val;}
else if(val!=0.0) {ans.clear(); return ans;}
piv++;
}
return ans;
}
};
Matrix fastexp(Matrix A, ll e) //O(N^3loge)
{
if(A.N!=A.M) {Matrix ANS; return ANS;}
if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexp(*(A.Inv),-e);}}
if(e==0)
{Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=0.0;} else {ANS.a[i][j]=1.0;}}} return ANS;}
if(e%2LL==0)
{
Matrix V =fastexp(A,(ll) e/2LL); return (V*V);
}
else
{
Matrix V=fastexp(A,(ll) e/2LL); return (V*V*A);
}
}
template<class T=ll>
class SparseTable //Range Minimum Queries
{
public:
ll N;
vector<T> a;
vector<vector<T> > v;
SparseTable() {N=0LL;}
SparseTable(vector<T> b)
{
a=b; N=a.size();
ll lo=(ll) floor((double) log2(N)) +1LL;
vector<T> xx;
REP(i,0,lo) {xx.pb(mp(INF,INF));} REP(i,0,N) {v.pb(xx);}
REP(step,0LL,lo)
{
REP(i,0,N-(1LL<<step)+1LL)
{
if(step==0) {v[i][0]=a[i];}
else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
}
}
}
T query(ll l, ll r)
{
ll step=(ll) floor((double) log2(r-l+1LL));
return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
}
};
class DSU
{
public:
ll N;
vector<ll> p,siz;
DSU(ll n)
{
N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
}
ll find(ll x)
{
if(p[x]==x) {return x;}
ll ans=find(p[x]);
p[x]=ans;
return ans;
}
void unionn(ll a, ll b)
{
a=find(a); b=find(b);
if(siz[a]>siz[b]) {swap(a,b);}
p[a]=b; siz[b]+=siz[a];
}
};
class SucPath
{
public:
ll N;
vector<ll> fo;
vector<vector<ll> > f2; //sparse table of steps powers of 2
ll ms; //max_steps
SucPath() {N=0LL;}
SucPath(vector<ll> x, ll max_steps)
{
N=x.size(); fo=x; ms=max_steps;
vector<ll> xx;
REP(i,0,(ll) (floor(log2(ms)))+1LL) {xx.pb(0LL);}
REP(i,0,N) {f2.pb(xx);}
Conf2(0);
}
void Conf2(ll e) //O(NlogN)
{
if((1LL<<e)>ms) {return;}
if(e==0) {REP(i,0,N) {f2[i][e]=fo[i];} Conf2(e+1);}
else
{
REP(i,0,N)
{
f2[i][e]=f2[f2[i][e-1]][e-1];
}
}
Conf2(e+1);
}
ll f(ll x,ll s) //O(logN)
{
ll ind=0;
while(s>0)
{
if(s%2!=0) {x=f2[x][ind];}
s/=2; ind++;
}
return x;
}
pl cycle() //Floyd's Algorithm, O(N) time, O(1) memory, return <element of cycle,length od cycle>
{
ll a=fo[0]; ll b=fo[fo[0]];
while(a!=b) {a=fo[a]; b=fo[fo[b]];}
ll l=1; b=fo[a];
while(b!=a) {b=fo[b]; l++;}
return mp(a,l);
}
};
class FT
{
public:
ll N;
vector<ll> a, f;
FT(vector<ll> z)
{
N = z.size(); a = z; ll sum = 0;
vector<ll> ps; ps.pb(0); REP(i,0,N) {sum+=a[i]; ps.pb(sum);}
REP(i,0,N+1)
{
f.pb(ps[i] - ps[i-(i&(-i))]);
}
}
ll sum(ll s)
{
if(s<0) {return 0;}
ll cur = s+1;
ll ans = 0;
while(cur>0)
{
ans+=f[cur];
cur-=(cur&(-cur));
}
return ans;
}
void update(ll s, ll dif)
{
ll cur = s+1;
a[s]+=dif;
while(cur<=N)
{
f[cur]+=dif;
cur+=(cur&(-cur));
}
}
};
class ST
{
public:
ll N;
class SV //seg value
{
public:
ll a;
SV() {a=0LL;}
SV(ll x) {a=x;}
SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
};
class LV //lazy value
{
public:
ll a;
LV() {a=0LL;}
LV(ll x) {a=x;}
LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
};
SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
{
SV X(p[c].a+(range[c].ss-range[c].ff+1)*lazy[c].a);
return X;
}
SV neuts; LV neutl;
vector<SV> p;
vector<LV> lazy;
vector<pl> range;
ST() {N=0LL;}
ST(vector<ll> arr)
{
N = (ll) 1<<(ll) ceil(log2(arr.size()));
REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
REP(i,0,N) {p.pb(neuts);}
REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
ll cur = N-1;
while(cur>0)
{
p[cur]=p[2*cur]&p[2*cur+1];
range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
cur--;
}
REP(i,0,2*N) {lazy.pb(neutl);}
}
void prop(ll c) //how lazy values propagate
{
p[c]=upval(c);
lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
lazy[c]=neutl;
}
SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b,1)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(c);}
prop(c);
SV ans = query(a,b,2*c)&query(a,b,2*c+1);
return ans;
}
void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return ;}
if(x>=a && y<=b)
{
lazy[c]=s&lazy[c];
return;
}
update(s,a,b,2*c); update(s,a,b,2*c+1);
p[c]=upval(2*c)&upval(2*c+1);
}
};
class DynamicST
{
public:
ll N;
class SV //seg value
{
public:
ll a;
SV() {a=0LL;}
SV(ll x) {a=x;}
SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
};
class LV //lazy value
{
public:
ll a;
LV() {a=0LL;}
LV(ll x) {a=x;}
LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
};
SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
{
SV X((m[c]->sv).a+(m[c]->r-m[c]->l+1)*(m[c]->lv).a);
return X;
}
SV neuts; LV neutl;
class node
{
public:
ll ind;
SV sv; LV lv;
ll l,r; //range
node * par, *lson, *rson;
node(ll ind2, SV sv2, LV lv2, unordered_map<ll,node *> *m)
{
ind=ind2; sv=sv2; lv=lv2; lson=nullptr; rson=nullptr;
if(ind==1) {l=0LL;par=nullptr;}
else
{
node * X = (*m)[ind/2];
par=X;
if(ind%2==0)
{
par->lson=this;
l=X->l; r=(X->l+X->r)/2LL;
}
else
{
par->rson=this;
l=(X->l+X->r+1)/2; r=X->r;
}
}
}
};
unordered_map<ll,node *> m;
node *root;
DynamicST(ll n)
{
N = (ll) 1<<(ll) ceil(log2(n));
node *X = new node(1,neuts,neutl,&m);
root=X; root->r=N-1LL;
}
void prop(ll c) //how lazy values propagate
{
m[c]->sv=upval(c);
if(m[c]->lson==nullptr) {node *X=new node(2*c,neuts,neutl,&m);}
if(m[c]->rson==nullptr) {node *X=new node(2*c+1,neuts,neutl,&m);}
m[2*c]->lv=m[c]->lv&m[2*c]->lv; m[2*c+1]->lv=m[c]->lv&m[2*c+1]->lv;
m[c]->lv=neutl;
if(2*c>=N)
{
m[2*c]->sv=upval(2*c); m[2*c+1]->sv=upval(2*c+1);
m[2*c]->lv=neutl; m[2*c+1]->lv=neutl;
}
}
SV query(ll a,ll b, ll c) //range [a,b], current node. initially: query(a,b,1)
{
ll x=m[c]->l; ll y=m[c]->r;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(c);}
prop(c);
SV ans = query(a,b,2*c)&query(a,b,2*c+1);
return ans;
}
void update(LV s, ll a, ll b, ll c) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
{
ll x=m[c]->l; ll y=m[c]->r;
if(y<a || x>b) {return ;}
if(x>=a && y<=b)
{
m[c]->lv=s&m[c]->lv;
if(c>=N) {m[c]->sv=upval(c); m[c]->lv=neutl;}
return;
}
if(m[c]->lson==nullptr) {node *X=new node(2*c,neuts,neutl,&m);}
if(m[c]->rson==nullptr) {node *X=new node(2*c+1,neuts,neutl,&m);}
update(s,a,b,2*c); update(s,a,b,2*c+1);
m[c]->sv=upval(2*c)&upval(2*c+1);
}
};
class PersistentST
{
public:
ll N;
class SV //seg value
{
public:
ll a;
SV() {a=0LL;}
SV(ll x) {a=x;}
SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
};
class LV //lazy value
{
public:
ll a;
LV() {a=0LL;}
LV(ll x) {a=x;}
LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
};
SV neuts; LV neutl;
class node
{
public:
ll ind;
SV sv; LV lv;
ll l,r; //range
ll rootind; //x: this node is root[x]
node *lson, *rson;
node(ll ind,node *par, SV sv2, LV lv2, ll rootindex=-1LL)
{
rootind=rootindex;
sv=sv2; lv=lv2; lson=nullptr; rson=nullptr;
if(par==nullptr) {l=0LL;}
else
{
if(ind%2==0)
{
par->lson=this;
l=par->l; r=(par->l+par->r)/2LL;
}
else
{
par->rson=this;
l=(par->l+par->r+1)/2; r=par->r;
}
}
}
};
SV upval(node *X) //how lazy values modify a seg value inside a node, c=current node
{
SV ANS((X->sv).a+(X->r-X->l+1)*(X->lv).a);
return ANS;
}
vector<node*> root;
vector<ll> anc; //ancestor of a seg tree copy
unordered_map<ll,node*> m; //stores current update
PersistentST(ll n)
{
N = (ll) 1<<(ll) ceil(log2(n));
node *X = new node(1LL,nullptr,neuts,neutl,0LL);
X->r=N-1LL;
root.pb(X);
anc.pb(0LL);
m[0]=nullptr;
}
void Build(node *cur) //goes from dynamic to fixed (except for persistence). init: Build(root[x])
{
if(cur->ind>=N) {return;}
node *X = new node(2*cur->ind,cur,neuts,neutl);
node *Y = new node(2*cur->ind+1,cur,neuts,neutl);
Build(X);
Build(Y);
}
void prop(node *cur) //how lazy values propagate
{
cur->sv=upval(cur);
if(cur->lson==nullptr) {node *X=new node(2*cur->ind,cur,neuts,neutl);}
if(cur->rson==nullptr) {node *X=new node(2*cur->ind+1,cur,neuts,neutl);}
node *X=cur->lson; node *Y=cur->rson;
X->lv=cur->lv&X->lv; Y->lv=cur->lv&Y->lv;
cur->lv=neutl;
if(2*cur->ind>=N)
{
X->sv=upval(X); Y->sv=upval(Y);
X->lv=neutl; Y->lv=neutl;
}
}
SV query(ll a,ll b, node *cur) //range [a,b], current node. initially: query(a,b,root[x]) for a query in seg tree number x
{
ll x=cur->l; ll y=cur->r;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(cur);}
prop(cur);
SV ans = query(a,b,cur->lson)&query(a,b,cur->rson);
return ans;
}
void CreateCopy(node *cur)
{
node *X = new node(cur->ind,m[cur->ind/2],cur->sv,cur->lv);
X->lson=cur->lson; X->rson=cur->rson;
m[cur->ind]=X;
if(cur->ind==1) {X->rootind=root.size(); root.pb(X); anc.pb(cur->rootind);}
}
void update(LV s, ll a, ll b, node *cur) //update LV, range [a,b], current node, current range. initially: update(s,a,b,0,S.N-1,root[x]). This will create a new seg tree version.
{
ll x=cur->l; ll y=cur->r;
if(y<a || x>b) {return;}
CreateCopy(cur);
node *X=m[cur->ind];
if(x>=a && y<=b)
{
X->lv=s&X->lv;
if(X->ind>=N) {X->sv=upval(X); X->lv=neutl;}
return;
}
if(cur->lson==nullptr) {node *Z=new node(2*cur->ind,cur,neuts,neutl);}
if(cur->rson==nullptr) {node *Z=new node(2*cur->ind+1,cur,neuts,neutl);}
update(s,a,b,cur->lson); update(s,a,b,cur->rson);
X->sv=upval(cur->lson)&upval(cur->rson);
}
};
class WDiGraph
{
public:
ll N;
vector<vector<pl> > adj;
vector<bool> visited;
vector<ll> current; //for CC
vector<bool> c; //for Bip
bool bip; //for Bip
vector<ll> TS;//Top Sort
vector<ll> SCC; //Attributes a number to each node
vector<vector<pl> > adjK; //reverse graph, for Kosaraju
vector<bool> pr; //for Djikstra
vector<ll> nv; //for Floyd
vector<bool> deleted; //dynamic graph
vector<unordered_set<ll> > adjs,adjr; //dynamic graph
unordered_map<pl,ll,hash_pair> we; //dynamic graph
vector<vector<pl> > adjFlow; //MaxFlow
unordered_map<pl,ll,hash_pair> m; //MaxFlow, m[(a,b)]=index of adjFlow[a] where b is stored, works for adj as well
unordered_map<pl,bool,hash_pair> exist; //maxFlow
ll src,ter; //MaxFlow, source and terminator/sink
bool reached; //MaxFlow
ll pathflow; //MaxFlow
vector<ll> lev; //Layered_Network,MaxFlow
vector<ll> nxted; //Dinics
Matrix Madj;
WDiGraph(vector<vector<pl> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {pr.pb(false); nv.pb(0); visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
vector<pl> xx; REP(i,0,N) {adjK.pb(xx);}
REP(i,0,adj.size())
{
REP(j,0,adj[i].size()) {adjK[adj[i][j].ff].pb(mp(i,adj[i][j].ss));}
}
unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); adjr.pb(em);}
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
adjs[i].insert(adj[i][j].ff);
adjr[adj[i][j].ff].insert(i);
we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
}
}
REP(i,0,N) {deleted.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
unordered_set<ll>::iterator it;
REP(i,0,N) {adj[i].clear();it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(mp(*it,we[mp(i,*it)])); it++;}}
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i].ff]) {c[adj[s][i].ff]=(c[s]+1)%2; DFS(adj[s][i].ff);}
else if(c[adj[s][i].ff]==c[s]) {bip=false;}
}
current.pb(s); //only needed for Kosaraju
return;
}
vector<ll> BFS(ll s)
{
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i].ff])
{
visited[adj[cur][i].ff]=true;
d.pb(adj[cur][i].ff);
distance[adj[cur][i].ff]=distance[cur]+1;
}
}
}
return distance;
}
bool Bip()
{
c[0]=0;
bip=true;
DFS(0);
if(bip) {return true;}
else {return false;}
}
void DFSTS(ll s)
{
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i].ff]) {DFSTS(adj[s][i].ff);}
}
visited[s]=true;
}
void TopSort()
{
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFSTS(i);
}
reverse(TS.begin(),TS.end());
}
void DFSK(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adjK[s].size())
{
if(!visited[adjK[s][i].ff]) {DFSK(adjK[s][i].ff);}
}
current.pb(s); //only needed for Kosaraju
return;
}
void Kosaraju()
{
if(SCC[0]!=-1) {return;}
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFS(i);
}
vector<ll> List=current;
Reset();
ll c=0LL;
for(ll i=N-1LL;i>=0LL;i--)
{
ll node=List[i];
if(visited[node]) {continue;}
DFSK(node);
REP(j,0,current.size()) {SCC[current[j]]=c;}
c++;
current.clear();
}
}
WDiGraph SCCGraph()
{
Kosaraju();
set<pair<pl,ll> > ed;
REP(i,0,adj.size())
{
REP(j,0,adj[i].size())
{
ed.insert(mp(mp(SCC[i],SCC[adj[i][j].ff]),adj[i][j].ss));
}
}
vector<vector<pl> > a; vector<pl> xx;
ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
REP(i,0,nscc) {a.pb(xx);}
set<pair<pl,ll> >::iterator it=ed.begin();
pair<pl,ll> cur; pl last=mp(-1,-1);
while(it!=ed.end())
{
cur=*it;
if(cur.ff!=last && cur.ff.ff!=cur.ff.ss) {a[cur.ff.ff].pb(mp(cur.ff.ss,cur.ss)); } //only shortes paths are relevant
last=cur.ff;
it++;
}
WDiGraph ans(a);
return ans;
}
vector<ll> Djikstra(ll s)
{
Reset();
vector<ll> d; REP(i,0,N) {d.pb(INF);}
d[s]=0;
priority_queue<pl> q;
q.push(mp(0,s));
ll cur;
while(!q.empty())
{
cur=q.top().ss; q.pop();
if(pr[cur]) {continue;}
pr[cur]=true;
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
{
d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
}
}
}
return d;
}
vector<pl> Djikstra_MS(vector<ll> sn) //Djikstra Multi-sourced, ans[i].ff=d(i,sn), ans[i].ss=member of sn closest to i
{
Reset();
ll K=sn.size();
vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
priority_queue<pl> q;
REP(i,0,K) {q.push(mp(0,sn[i]));}
ll cur;
while(!q.empty())
{
cur=q.top().ss; q.pop();
if(pr[cur]) {continue;}
pr[cur]=true;
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
{
d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
d[adj[cur][i].ff].ss=d[cur].ss;
q.push(mp(-d[adj[cur][i].ff].ff,adj[cur][i].ff));
}
}
}
return d;
}
vector<ll> SPFA(ll s)
{
Reset();
vector<ll> d; REP(i,0,N) {d.pb(INF);}
d[s]=0;
deque<ll> tv; tv.pb(s); pr[s]=true;
ll cur; ll mv=0;
while(!tv.empty())
{
cur=tv.front(); tv.pop_front(); pr[cur]=false;
nv[cur]++; mv=max(mv,nv[cur]);
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
{
d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
pr[adj[cur][i].ff]=true;
}
}
if(mv>=N) {d.clear(); break;} //negative cycle
}
return d;
}
vector<pl> SPFA_MS(vector<ll> sn)
{
ll K=sn.size();
Reset();
vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
deque<ll> tv; REP(i,0,K) {tv.pb(sn[i]); pr[sn[i]]=true;}
ll cur; ll mv=0;
while(!tv.empty())
{
cur=tv.front(); tv.pop_front(); pr[cur]=false;
nv[cur]++; mv=max(mv,nv[cur]);
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
{
d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
d[adj[cur][i].ff].ss=d[cur].ss;
if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
pr[adj[cur][i].ff]=true;
}
}
if(mv>=N) {d.clear(); break;} //negative cycle
}
return d;
}
vector<vector<ll> > Floyd() //assumes there is no neg cycle
{
Reset();
vector<vector<ll> > d; vector<ll> xx; REP(i,0,N) {xx.pb(INF);} REP(i,0,N) {d.pb(xx);}
REP(i,0,N)
{
d[i][i]=0;
REP(j,0,adj[i].size())
{
d[i][adj[i][j].ff]=adj[i][j].ss;
}
}
REP(i,0,N)
{
REP(q1,0,N)
{
REP(q2,0,N)
{
if(q1==q2) {continue;}
d[q1][q2]=min(d[q1][q2],d[q1][i]+d[i][q2]);
}
}
}
return d;
}
void erase_edge(pl edge)
{
adjs[edge.ff].erase(edge.ss); adjr[edge.ss].erase(edge.ff);
}
void add_edge(pair<pl,ll> edge)
{
if(adjs[edge.ff.ff].find(edge.ff.ss)==adjs[edge.ff.ff].end())
{
we[edge.ff]=edge.ss;
adjs[edge.ff.ff].insert(edge.ff.ss); adjr[edge.ff.ss].insert(edge.ff.ff);
}
else
{
we[edge.ff]+=edge.ss;
}
}
void erase_node(ll s)
{
deleted[s]=true;
unordered_set<ll>::iterator it; it=adjs[s].begin(); vector<pl> e;
while(it!=adjs[s].end())
{
e.pb(mp(s,*it));
it++;
}
REP(i,0,e.size()) {erase_edge(e[i]);}
}
void add_node(vector<pl> in, vector<pl> out) // adds node with adjacency list con, and index N
{
N++; pr.pb(false); nv.pb(0); deleted.pb(false); unordered_set<ll> em; vector<pl> emm; adjs.pb(em); adj.pb(emm);
REP(i,0,in.size()) {add_edge(mp(mp(in[i].ff,N-1),in[i].ss));}
REP(i,0,out.size()) {add_edge(mp(mp(N-1,out[i].ff),out[i].ss));}
}
void RGConstructor(ll source, ll terminator) //Constructs Residual Grap, adjFlow, map m
{
src=source; ter=terminator;
adjFlow=adj;
REP(i,0,N)
{
REP(j,0,adj[i].size()) {m[mp(i,adj[i][j].ff)]=j; exist[mp(i,adj[i][j].ff)]=true;}
}
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
if(!exist[mp(adj[i][j].ff,i)]) {adjFlow[adj[i][j].ff].pb(mp(i,0LL)); m[mp(adj[i][j].ff,i)]=adjFlow[adj[i][j].ff].size()-1;}
}
}
REP(i,0,N) {lev.pb(-1); nxted.pb(0LL);}
}
void ResetFlow()
{
REP(i,0,N) {visited[i]=false;}
pathflow=0LL; reached=false;
}
void BFSFlow(ll s) //builds Layered Network
{
Reset();
REP(i,0,N) {lev[i]=INF;}
REP(i,0,N) {visited[i]=false;}
lev[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adjFlow[cur].size())
{
ll node=adjFlow[cur][i].ff;
if(!visited[node] && adjFlow[cur][i].ss>0LL)
{
visited[node]=true;
d.pb(node);
lev[node]=lev[cur]+1;
}
}
}
}
void DFSFlow1(ll s, ll flow, ll D) //Scaling
{
if(reached) {return;}
if(visited[s]) {return;}
ll node,we;
if(s==ter) {reached=true; pathflow=flow; return;}
visited[s]=true;
REP(i,0,adjFlow[s].size())
{
node=adjFlow[s][i].ff; we=adjFlow[s][i].ss;
if(visited[node]) {continue;}
if(we<D) {continue;}
DFSFlow1(node,min(flow,we),D);
if(reached)
{
adjFlow[s][i].ss-=pathflow;
adjFlow[node][m[mp(node,s)]].ss+=pathflow;
break;
}
}
return;
}
void DFSFlow2(ll s, ll flow) //Dinics
{
if(reached) {return;}
if(visited[s]) {return;}
ll node,we;
if(s==ter) {reached=true; pathflow=flow; return;}
visited[s]=true;
REP(i,nxted[s],adjFlow[s].size())
{
node=adjFlow[s][i].ff; we=adjFlow[s][i].ss;
if(visited[node]) {continue;}
if(we==0) {continue;}
if(lev[node]<=lev[s]) {nxted[s]++;continue;}
DFSFlow2(node,min(flow,we));
if(reached)
{
adjFlow[s][i].ss-=pathflow;
if(adjFlow[s][i].ss==0) {nxted[s]++;}
adjFlow[node][m[mp(node,s)]].ss+=pathflow;
break;
}
nxted[s]++;
}
return;
}
ll MF_Scaling(ll source, ll terminator) //min(O(E*MaxFlow),O(E^2*log(Emax))), prefered choice for weighted
{
RGConstructor(source,terminator);
ll flow=0LL; ll D=0LL; REP(i,0,N) {REP(j,0,adjFlow[i].size()) {D=max(D,adjFlow[i][j].ss);}}
while(D>0LL)
{
ResetFlow(); DFSFlow1(src,INF,D);
if(reached) {flow+=pathflow;}
else {D=D/2LL;}
}
return flow;
}
ll MF_Dinic(ll source, ll terminator) //O(EV^2), specil case unweighted graph: min(O(EV^2/3),O(E^3/2)), special case unit network: O(EV^1/2)
{
RGConstructor(source,terminator);
ll flow=0LL; bool al=true;
while(1>0)
{
ResetFlow(); DFSFlow2(src,INF);
if(reached) {al=true; flow+=pathflow;}
else if(!al) {break;}
else {REP(i,0,N) {nxted[i]=0LL;} al=false; BFSFlow(src);}
}
return flow;
}
vector<pl> MinCut(ll source, ll terminator)
{
MF_Dinic(source, terminator);
ResetFlow(); DFSFlow1(src,INF,1);
vector<pl> ans;
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
if(visited[i] && !visited[adj[i][j].ff]) {ans.pb(mp(i,adj[i][j].ff));}
}
}
return ans;
}
Matrix SMul(Matrix A, Matrix B)
{
if(A.M!=B.N) {Matrix ANS; return ANS;}
vector<double> xx; vector<vector<double> > ans; REP(i,0,B.M) {xx.pb((double) (INF));} REP(i,0,A.N) {ans.pb(xx);}
REP(i,0,A.N)
{
REP(j,0,B.M)
{
double val=(double) INF;
REP(k,0,A.M) {val=min(val,A.a[i][k]+B.a[k][j]);}
ans[i][j]=val;
}
}
Matrix ANS(ans); return ANS;
}
Matrix fastexpS(Matrix A, ll e) //O(N^3loge)
{
if(A.N!=A.M) {Matrix ANS; return ANS;}
if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexpS(*(A.Inv),-e);}}
if(e==0)
{Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=(double) INF;} else {ANS.a[i][j]=0.0;}}} return ANS;}
if(e%2LL==0)
{
Matrix V =fastexpS(A,(ll) e/2LL); return SMul(V,V);
}
else
{
Matrix V=fastexpS(A,(ll) e/2LL); return SMul(SMul(V,V),A);
}
}
void Build_Madj()
{
if(Madj.N!=0LL) {return;}
vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb((double) (INF));} REP(i,0,N) {madj.pb(xx);}
REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j].ff]=(double) (adj[i][j].ss);}}
Matrix B(madj); Madj=B;
}
double SP(ll a, ll b, ll length) //shortest path between a,b with fixed length, O(N^3loglength)
{
Build_Madj();
return (fastexpS(Madj,length).a[a][b]);
}
};
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<ll> visited; //for DFS/BFS
vector<ll> current; //for CC
vector<bool> c; //for Bip
bool bip; //for Bip
unordered_map<pair<vector<bool>,ll>,vector<ll>,hash_pair> mH; //for Hamiltonian
vector<list<ll> > ad; //for Hierholzer
unordered_map<pl,bool,hash_pair> valid; //for Hierholzer
Matrix Madj;
vector<ll> og; //node i points to value og[i]
vector<vector<ll> > dfs_tree;
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
current.pb(s); //only needed for CC
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
else if(c[adj[s][i]]==c[s]) {bip=false;}
}
return;
}
void DFS_Tree(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {dfs_tree[s].pb(adj[s][i]); dfs_tree[adj[s][i]].pb(s); DFS_Tree(adj[s][i]);}
}
return;
}
bool Connected()
{
Reset();
DFS(0);
REP(i,0,N) {if(!visited[i]) {return false;}}
return true;
}
vector<ll> BFS(ll s)
{
Reset();
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i]])
{
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]]=distance[cur]+1;
}
}
}
return distance;
}
vector<pl> BFS_MS(vector<ll> sn) //multi-sourced BFS, ans[i].ff=d(i,starting nodes), ans[i].ss=starting node closer to i
{
Reset();
ll K=sn.size();
vector<pl> distance; REP(i,0,N) {distance.pb(mp(INF,-1LL));}
REP(i,0,N) {visited[i]=false;}
REP(i,0,K) {distance[sn[i]]=mp(0LL,sn[i]); visited[sn[i]]=true;}
deque<ll> d; REP(i,0,K) {d.pb(sn[i]);} ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(visited[adj[cur][i]]) {continue;}
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]].ff=distance[cur].ff+1;
distance[adj[cur][i]].ss=distance[cur].ss;
}
}
return distance;
}
vector<vector<ll> > CC()
{
Reset();
ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
vector<vector<ll> > ans;
while(missing>0)
{
REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
current.clear();
DFS(fi);
ans.pb(current);
missing-=current.size();
}
return ans;
}
vector<Graph> CCG()
{
Reset();
vector<Graph> ans;
vector<vector<ll> > CC=(*this).CC();
unordered_map<ll,ll> m;vector<ll> xx; vector<vector<ll> > ad;
vector<ll> ma;
REP(cc,0,CC.size())
{
m.clear(); ma.clear();
ad.clear();
ll NN=CC[cc].size();
REP(i,0,NN) {ad.pb(xx);}
REP(i,0,NN) {m[CC[cc][i]]=i; ma[i]=ma[CC[cc][i]];}
ll a,b;
REP(i,0,NN)
{
a=CC[cc][i];
REP(j,0,adj[a].size()) {b=adj[a][j]; ad[i].pb(m[b]);}
}
Graph H(ad); H.og=ma;
ans.pb(H);
}
return ans;
}
bool Bip()
{
Reset();
bip=true;
REP(i,0,N)
{
if(visited[i]) {continue;}
c[i]=0LL; DFS(i);
}
if(bip) {return true;}
else {return false;}
}
bool Eulerian()
{
Reset();
REP(i,0,N) {if(adj[i].size()%2!=0) {return false;}}
return true;
}
vector<ll> Hamiltonian()
{
bool Ore=true;
vector<bool> v; REP(i,0,N) {v.pb(true);}
REP(i,0,N)
{
REP(j,0,N) {v[j]=true;}
v[i]=false;
REP(j,0,adj[i].size()) {v[adj[i][j]]=false;}
REP(j,0,N)
{
if(v[j] && adj[i].size()+adj[j].size()<N) {Ore=false; break;}
}
}
if(Ore) {return Palmer();}
REP(i,0,N) {v[i]=true;}
REP(i,0,N)
{
if(!f(v,i).empty()) {return f(v,i);}
}
vector<ll> ans; return ans;
}
vector<ll> f(vector<bool> v, ll x) //O(N^2*2^N), for when we dont know anything about the graph
{
if(!mH[mp(v,x)].empty()) {return mH[mp(v,x)];}
ll oc=0LL; REP(i,0,N) {if(v[i]) {oc++;}}
vector<ll> ans;
if(oc==1) {ans.pb(x);}
else
{
v[x]=false; ll node;
REP(i,0,adj[x].size())
{
node=adj[x][i];
if(!v[node]) {continue;}
vector<ll> p=f(v,node);
if(!p.empty()) {p.pb(x); ans=p; break;}
}
}
mH[mp(v,x)]=ans;
return ans;
}
vector<ll> Palmer() //O(N^2), constructs Hamiltonian Cycle if Ore's condition is fullfilled
{
vector<ll> ans; REP(i,0,N) {ans.pb(i);}
vector<vector<bool> > madj; vector<bool> dummy; REP(i,0,N) {dummy.pb(false);} REP(i,0,N) {madj.pb(dummy);}
REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=true; madj[adj[i][j]][i]=true;}}
REP(cnt,0,N)
{
ll ind1=-1LL;
REP(i,0,N)
{
if(!madj[ans[i]][ans[(i+1)%N]]) {ind1=i; break;}
}
if(ind1==-1) {break;}
ll ind2=-1LL;
REP(j,0,N)
{
if(madj[ans[ind1]][ans[j]] && madj[ans[(ind1+1)%N]][ans[(j+1)%N]]) {ind2=j; break;}
}
REP(i,0,((ind2-ind1+N)%N +1)/2LL)
{
ll node1=(ind1+1+i)%N;
ll node2=(ind2-i)%N;
swap(ans[node1],ans[node2]);
}
}
return ans;
}
void Tour(ll s)
{
current.pb(s);
if(ad[s].size()==0) {return;}
ll nxt=*ad[s].begin();
while(!valid[mp(s,nxt)])
{
valid[mp(nxt,s)]=false; ad[s].erase(ad[s].begin());
if(ad[s].size()==0) {return;}
nxt=*ad[s].begin();
}
valid[mp(s,nxt)]=false; valid[mp(nxt,s)]=false;
ad[s].erase(ad[s].begin());
Tour(nxt);
}
vector<ll> Hierholzer()
{
ll nodd=0LL; REP(i,0,N) {if(adj[i].size()%2!=0) {nodd++;}}
list<ll> ans;
if(nodd>2LL) {vector<ll> xx; return xx;}
vector<vector<ll> > indiferent=CC(); ll nsb1=0LL;
REP(i,0,indiferent.size()) {if(indiferent[i].size()>1LL) {nsb1++;}}
if(nsb1>1LL) {vector<ll> xx; return xx;}
ll sn=0LL; REP(i,0,N) {if(adj[i].size()%2!=0) {sn=i;}}
list<ll> xx;
REP(i,0,N) {xx.clear(); xx.insert(xx.begin(),adj[i].begin(),adj[i].end()); ad.pb(xx);}
ans.insert(ans.begin(),sn);
list<ll>::iterator it=ans.begin();
REP(i,0,N) {REP(j,0,adj[i].size()) {valid.insert(mp(mp(i,adj[i][j]),true));}}
REP(i,0,INF)
{
if(it==ans.end()) {break;}
current.clear();
Tour(*it);
it=ans.erase(it);
it=ans.insert(it,current.begin(),current.end());
it++;
}
it=ans.begin();
vector<ll> f_ans; REP(i,0,ans.size()) {f_ans.pb(*it); it++;}
return f_ans;
}
ll MaxMatching()
{
if(!Bip()) {return -1;}
vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,N+2) {Wadj.pb(xx);}
REP(i,0,N)
{
if(c[i]==1) {Wadj[i].pb(mp(N+1,1)); continue;}
Wadj[N].pb(mp(i,1));
REP(j,0,adj[i].size())
{
Wadj[i].pb(mp(adj[i][j],1));
}
}
WDiGraph G(Wadj);
return G.MF_Dinic(N,N+1);
}
void Build_Madj()
{
if(Madj.N!=0LL) {return;}
vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {madj.pb(xx);}
REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=1.0;}}
Matrix B(madj); Madj=B;
}
ll cnt_path(ll a, ll b, ll length)
{
Build_Madj();
return fastexp(Madj,length).a[a][b];
}
};
class DynamicGraph
{
public:
ll N; ll nxt_id;
class node
{
public:
ll id; //unique non-negative integer id
unordered_set<ll> adj;
node() {id=-1;}
node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
};
unordered_map<ll,node> m;
unordered_set<ll> active_id; //active node ids
DynamicGraph(vector<vector<ll> > adj)
{
N=adj.size();
REP(i,0,N)
{
node X(i,adj[i]);
m[i]=X;
active_id.insert(i);
}
nxt_id=N;
}
void add_edge(pl edge)
{
m[edge.ff].adj.insert(edge.ss);
m[edge.ss].adj.insert(edge.ff);
}
void erase_edge(pl edge)
{
m[edge.ff].adj.erase(edge.ss);
m[edge.ss].adj.erase(edge.ff);
}
void add_node(vector<ll> ad)
{
N++; vector<ll> em;
node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
REP(i,0,ad.size())
{
add_edge(mp(nxt_id-1,ad[i]));
}
}
void erase_node(ll id)
{
N--;
vector<pl> toerase;
unordered_set<ll>::iterator it=m[id].adj.begin();
while(it!=m[id].adj.end())
{
toerase.pb(mp(id,*it)); it++;
}
REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
active_id.erase(id);
m.erase(id);
}
};
class DynamicDiGraph
{
public:
ll N; ll nxt_id;
class node
{
public:
ll id; //unique non-negative integer id
unordered_set<ll> adj;
unordered_set<ll> adjr;
node() {id=-1;}
node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
};
unordered_map<ll,node> m;
unordered_set<ll> active_id; //active node ids
DynamicDiGraph(vector<vector<ll> > adj)
{
N=adj.size();
REP(i,0,N)
{
node X;
m[i]=X;
active_id.insert(i);
}
nxt_id=N;
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
m[i].adj.insert(adj[i][j]);
m[adj[i][j]].adjr.insert(i);
}
}
}
void add_edge(pl edge)
{
m[edge.ff].adj.insert(edge.ss);
m[edge.ss].adjr.insert(edge.ff);
}
void erase_edge(pl edge)
{
m[edge.ff].adj.erase(edge.ss);
m[edge.ss].adjr.erase(edge.ff);
}
void add_node(vector<ll> in,vector<ll> out)
{
N++; vector<ll> em;
node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
REP(i,0,in.size())
{
add_edge(mp(in[i],nxt_id-1));
}
REP(i,0,out.size())
{
add_edge(mp(nxt_id-1,out[i]));
}
}
void erase_node(ll id)
{
N--;
vector<pl> toerase;
unordered_set<ll>::iterator it;
it=m[id].adj.begin();
while(it!=m[id].adj.end())
{
toerase.pb(mp(id,*it)); it++;
}
it=m[id].adjr.begin();
while(it!=m[id].adjr.end())
{
toerase.pb(mp(*it,id)); it++;
}
REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
active_id.erase(id);
m.erase(id);
}
};
class DynamicWG
{
public:
ll N; ll nxt_id;
unordered_map<pl,ll,hash_pair> we;
class node
{
public:
ll id; //unique non-negative integer id
unordered_set<ll> adj;
node() {id=-1;}
node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
};
unordered_map<ll,node> m;
unordered_set<ll> active_id; //active node ids
DynamicWG(vector<vector<pl> > adj)
{
N=adj.size();
vector<ll> em;
REP(i,0,N)
{
node X(i,em);
REP(j,0,adj[i].size()) {X.adj.insert(adj[i][j].ff); we[mp(i,adj[i][j].ff)]=adj[i][j].ss; we[mp(adj[i][j].ff,i)]=adj[i][j].ss;}
m[i]=X;
active_id.insert(i);
}
nxt_id=N;
}
void add_edge(pair<pl,ll> edge)
{
if(m[edge.ff.ff].adj.find(edge.ff.ss)!=m[edge.ff.ff].adj.end())
{
we[edge.ff]+=edge.ss; swap(edge.ff.ff,edge.ff.ss);
we[edge.ff]+=edge.ss;
}
else
{
m[edge.ff.ff].adj.insert(edge.ff.ss);
m[edge.ff.ss].adj.insert(edge.ff.ff);
we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss); we[edge.ff]=edge.ss;
}
}
void erase_edge(pl edge)
{
m[edge.ff].adj.erase(edge.ss);
m[edge.ss].adj.erase(edge.ff);
we.erase(edge);
}
void add_node(vector<pl> ad)
{
N++; vector<ll> em;
node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
REP(i,0,ad.size())
{
add_edge(mp(mp(nxt_id-1,ad[i].ff),ad[i].ss));
}
}
void erase_node(ll id)
{
N--;
vector<pl> toerase;
unordered_set<ll>::iterator it=m[id].adj.begin();
while(it!=m[id].adj.end())
{
toerase.pb(mp(id,*it)); it++;
}
REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
active_id.erase(id);
m.erase(id);
}
};
class DynamicWDiGraph
{
public:
ll N; ll nxt_id;
unordered_map<pl,ll,hash_pair> we;
class node
{
public:
ll id; //unique non-negative integer id
unordered_set<ll> adj;
unordered_set<ll> adjr;
node() {id=-1;}
node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
};
unordered_map<ll,node> m;
unordered_set<ll> active_id; //active node ids
DynamicWDiGraph(vector<vector<pl> > adj)
{
N=adj.size();
REP(i,0,N)
{
node X;
m[i]=X;
active_id.insert(i);
}
nxt_id=N;
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
m[i].adj.insert(adj[i][j].ff);
m[adj[i][j].ff].adjr.insert(i);
we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
}
}
}
void add_edge(pair<pl,ll> edge)
{
if(m[edge.ff.ff].adj.find(edge.ff.ss)!=m[edge.ff.ff].adj.end())
{
we[edge.ff]+=edge.ss;
}
else
{
m[edge.ff.ff].adj.insert(edge.ff.ss);
m[edge.ff.ss].adjr.insert(edge.ff.ff);
we[edge.ff]=edge.ss;
}
}
void erase_edge(pl edge)
{
m[edge.ff].adj.erase(edge.ss);
m[edge.ss].adjr.erase(edge.ff);
we.erase(edge);
}
void add_node(vector<pl> in,vector<pl> out)
{
N++; vector<ll> em;
node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
REP(i,0,in.size())
{
add_edge(mp(mp(in[i].ff,nxt_id-1),in[i].ss));
}
REP(i,0,out.size())
{
add_edge(mp(mp(nxt_id-1,out[i].ff),out[i].ss));
}
}
void erase_node(ll id)
{
N--;
vector<pl> toerase;
unordered_set<ll>::iterator it;
it=m[id].adj.begin();
while(it!=m[id].adj.end())
{
toerase.pb(mp(id,*it)); it++;
}
it=m[id].adjr.begin();
while(it!=m[id].adjr.end())
{
toerase.pb(mp(*it,id)); it++;
}
REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
active_id.erase(id);
m.erase(id);
}
};
class Tree
{
public:
ll N;
vector<ll> p;
vector<vector<ll> > sons;
vector<vector<ll> > adj;
ll root;
vector<bool> visited;
vector<ll> level; //starting in 0
vector<ll> sub; //number of nodes in subtree
vector<ll> val; //node values
vector<ll> DFSarr1; //DFS Array
vector<ll> DFSarr2; //DFS Array for LCA with whole path
vector<ll> pos; //inverted DFSArr, only for LCA
vector<pl> levDFSarr; //array of levels on DFSarr, only needed for LCA
vector<ll> sumto; //weighted graph, length of path root-->i
SparseTable<pl> S; //for LCA
SucPath P; //for function f
ll max_steps; //for function f
vector<ll> prufer; //Prufer code, defines a tree uniquely
vector<ll> dist;
pair<ll,pl> diametre;
unordered_set<ll> included; //create new tree
vector<vector<ll> > back_edge; //in the case this tree is a DFS-tree
vector<pl> bridge;
vector<ll> articulation_point;
vector<ll> high_be; //highest back_edge per node
vector<ll> high_sub; //highest back_edge in subtree
vector<vector<ll> > farthest_dir;
vector<ll> farthest_down;
vector<ll> farthest_up;
vector<ll> farthest;
Tree(vector<vector<ll> > ad, ll r=0LL)
{
N=ad.size(); root=r; adj=ad;
REP(i,0,N) {visited.pb(false);}
vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0); sub.pb(1LL); pos.pb(0LL); sumto.pb(0LL);}
DFS_Build(r,r);
REP(i,0,DFSarr2.size()) {pos[DFSarr2[i]]=i;}
REP(i,0,DFSarr2.size()) {levDFSarr.pb(mp(level[DFSarr2[i]],DFSarr2[i]));}
SparseTable<pl> X(levDFSarr); S=X;
max_steps=N;
SucPath Y(p,N); P=Y;
REP(i,0,N) {val.pb(0LL);}
vector<ll> xxx;
REP(i,0,N) {farthest_up.pb(0); farthest_down.pb(0); farthest_dir.pb(xxx); farthest.pb(0);}
REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS_Build(ll s, ll par)
{
DFSarr1.pb(s);
DFSarr2.pb(s);
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
visited[s]=true;
REP(i,0,adj[s].size())
{
if(adj[s][i]==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i],s);
sub[s]+=sub[adj[s][i]];
DFSarr2.pb(s);
}
return;
}
void DFS_sumto(ll s)
{
sumto[s]=sumto[p[s]]+val[s];
REP(i,0,sons[s].size())
{
DFS_sumto(sons[s][i]);
}
}
void DFS_distance(ll s, ll las)
{
REP(i,0,adj[s].size())
{
if(adj[s][i]==las) {continue;}
dist[adj[s][i]]=dist[s]+1;
DFS_distance(adj[s][i],s);
}
}
void distance(ll s)
{
dist.clear(); REP(i,0,N) {dist.pb(INF);}
dist[s]=0;
DFS_distance(s,s);
}
void Calc_Diametre()
{
distance(root);
vector<ll>::iterator it=max_element(whole(dist));
ll ind=it-dist.begin();
distance(ind);
diametre.ss.ff=ind;
it=max_element(whole(dist));
diametre.ss.ss=it-dist.begin();
diametre.ff=*it;
}
void DFS(ll s, ll las=-1LL)
{
REP(i,0,adj[s].size())
{
if(adj[s][i]==las) {continue;}
DFS(adj[s][i],s);
}
included.insert(s);
}
ll LCA(ll a, ll b)
{
a=pos[a]; b=pos[b];
ll l=min(a,b); ll r=max(a,b);
pl ans=S.query(l,r);
return ans.ss;
}
ll d1(ll a, ll b)
{
return level[a]+level[b]-2*level[LCA(a,b)];
}
ll d2(ll a, ll b)
{
return sumto[a]+sumto[b]-2*sumto[LCA(a,b)];
}
ll f(ll x, ll k)
{
return P.f(x,k);
}
vector<Tree> CC()
{
vector<Tree> ans;
Graph G(adj);
vector<Graph> CC_step=G.CCG();
REP(i,0,CC_step.size()) {Tree T(CC_step[i].adj,0); ans.pb(T);}
return ans;
}
void Build_Prufer() //O(N)
{
ll ptr=0LL; vector<bool> v; REP(i,0,N) {v.pb(true);}
vector<ll> nadj; REP(i,0,N) {nadj.pb(adj[i].size());}
ll leaf;
while(prufer.size()<N-2LL)
{
while(nadj[ptr]!=1LL && ptr<N) {ptr++;}
leaf=ptr;
while(leaf<=ptr && prufer.size()<N-2LL)
{
v[leaf]=false;
REP(i,0,adj[leaf].size()) {if(v[adj[leaf][i]]) {leaf=adj[leaf][i]; break;}}
prufer.pb(leaf);
nadj[leaf]--; if(nadj[leaf]>1) {break;}
}
ptr++;
}
return;
}
Tree Subtree(ll s)
{
included.clear();
DFS(s,p[s]);
unordered_map<ll,ll> m;
unordered_set<ll>::iterator it;
it=included.begin();
ll cnt=0LL;
while(it!=included.end())
{
m[*it]=cnt; cnt++; it++;
}
it=included.begin();
vector<ll> xx; vector<vector<ll> > ad;
REP(i,0,included.size()) {ad.pb(xx);}
REP(i,0,sons[s].size())
{
ad[0].pb(m[sons[s][i]]);
}
it++; cnt=1LL;
while(it!=included.end())
{
REP(i,0,adj[*it].size())
{
ad[cnt].pb(m[adj[*it][i]]);
}
it++; cnt++;
}
Tree ANS(ad);
return ANS;
}
Tree Uptree(ll s)
{
if(s==root) {vector<vector<ll> > adj; Tree T(adj); return T;}
included.clear();
DFS(p[s],s);
unordered_map<ll,ll> m;
unordered_set<ll>::iterator it;
it=included.begin();
ll cnt=0LL;
while(it!=included.end())
{
m[*it]=cnt; cnt++; it++;
}
it=included.begin();
vector<ll> xx; vector<vector<ll> > ad;
REP(i,0,included.size()) {ad.pb(xx);}
cnt=0LL;
while(it!=included.end())
{
REP(i,0,adj[*it].size())
{
if(adj[*it][i]==s) {continue;}
ad[cnt].pb(m[adj[*it][i]]);
}
it++; cnt++;
}
Tree ANS(ad);
return ANS;
}
vector<Tree> Split(ll s) //forest created by removing node s
{
vector<Tree> ANS;
REP(i,0,sons[s].size())
{
ANS.pb(Subtree(sons[s][i]));
}
if(s!=root) {ANS.pb(Uptree(s));}
return ANS;
}
ll centroid()
{
REP(i,0,N)
{
ll max_tree = 0LL;
REP(j,0,sons[i].size()) {max_tree=max(max_tree,sub[sons[i][j]]);}
max_tree=max(max_tree,N-sub[i]);
if(max_tree<=N/2) {return i;}
}
return 0LL;
}
class HeavyPath
{
public:
ll N;
ll low, high;
Tree *T;
ST S;
HeavyPath() {N=0LL;}
HeavyPath(ll x, ll y, Tree *K)
{
T=K;
low=x; high=y;
if(T->level[x]<T->level[y]) {swap(high,low);}
N = T->level[x]-T->level[y]+1LL;
vector<ll> st_val; ll c = low;
while(1>0) {st_val.pb(T->val[c]); if(c==high) {break;} c=T->p[c];}
ST R(st_val); S=R;
}
ll pos(ll x)
{
return (T->level[low]-T->level[x]);
}
ST::SV query(ll ind1, ll ind2)
{
return S.query(ind1,ind2);
}
void update(ST::LV X, ll ind1, ll ind2)
{
S.update(X,ind1,ind2);
}
};
vector<HeavyPath *> h_path; //heavy paths
unordered_map<ll,HeavyPath *> HP; //m[s] = heavy path including s
void HLD()
{
vector<ll> large; ll c;
REP(i,0,N)
{
ll node=-1; ll ls = -1LL;
REP(j,0,sons[i].size())
{
c=sons[i][j];
if(sub[c]>=ls) {ls=sub[c]; node=c;}
}
large.pb(node);
}
REP(i,0,N)
{
if(sons[i].size()>0) {continue;}
c=i;
while(c!=root && c==large[p[c]]) {c=p[c];}
HeavyPath *P = new HeavyPath(i,c,this);
c=i; while(1>0) {HP[c]=P; if(c==P->high) {break;} c=p[c];}
h_path.pb(P);
}
}
ST::SV query_ancestor(ll s, ll anc)
{
ST::SV ans;
if(level[s]<level[anc]) {return ans;}
ll c = s;
while(1>0)
{
ST::SV thispath;
if(level[HP[c]->high]>=level[anc])
{
thispath = HP[c]->query(HP[c]->pos(c),HP[c]->N-1);
}
else
{
thispath = HP[c]->query(HP[c]->pos(c),HP[c]->pos(anc));
}
ans=ans&thispath;
c=HP[c]->high; c=p[c];
if(c==root || level[c]<level[anc]) {break;}
}
return ans;
}
ST::SV query(ll a, ll b) //query along path a->b
{
ll lca = LCA(a,b);
ST::SV V1 = query_ancestor(a,lca);
ST::SV V2; if(b!=lca) {V2= query_ancestor(b,f(b,level[b]-level[lca]-1LL));}
return V1&V2;
}
void update_ancestor(ST::LV X, ll s, ll anc)
{
if(level[s]<level[anc]) {return;}
ll c = s;
while(1>0)
{
if(level[HP[c]->high]>=level[anc])
{
HP[c]->update(X,HP[c]->pos(c),HP[c]->N-1);
}
else
{
HP[c]->update(X,HP[c]->pos(c),HP[c]->pos(anc));
}
c=HP[c]->high; if(c==root) {break;} c=p[c];
if(level[c]<level[anc]) {break;}
}
}
void update(ST::LV X, ll a, ll b)
{
ll lca = LCA(a,b);
update_ancestor(X,a,lca);
if(b!=lca) {update_ancestor(X,b,f(b,level[b]-level[lca]-1LL));}
}
void High_Sub(ll s)
{
REP(i,0,sons[s].size()) {High_Sub(sons[s][i]);}
REP(i,0,sons[s].size()) {ll c=sons[s][i]; high_sub[s]=min(high_sub[s],high_sub[c]);}
}
void Init_Back_Edge(vector<vector<ll> > be)
{
back_edge=be;
REP(i,0,N) {high_be.pb(level[i]); high_sub.pb(level[i]);}
REP(i,0,N)
{
REP(j,0,back_edge[i].size())
{
ll c = back_edge[i][j];
high_be[i]=min(high_be[i],level[c]);
}
}
REP(i,0,N) {high_sub[i]=high_be[i];}
High_Sub(root);
}
void FindBridge()
{
REP(i,0,N)
{
if(i==root) {continue;}
if(high_sub[i]==level[i]) {bridge.pb(mp(i,p[i]));}
}
}
void FindArticulationPoint()
{
REP(i,0,N)
{
bool include=false;
if(i==root)
{
if(sons[i].size()>1LL) {articulation_point.pb(i);}
continue;
}
REP(j,0,sons[i].size())
{
ll c = sons[i][j];
if(high_sub[c]==level[c]) {include=true;}
}
if(include) {articulation_point.pb(i);}
}
}
void Calc_farthest_down(ll s)
{
REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i]);}
REP(i,0,adj[s].size())
{
if(adj[s][i]==p[s]) {continue;}
farthest_dir[s][i]=farthest_down[adj[s][i]]+val[adj[s][i]];
farthest_down[s]=max(farthest_down[s],farthest_dir[s][i]);
}
}
void Calc_farthest_up(ll s)
{
if(s==root) {farthest_up[s]=0LL;}
pl best_dis=mp(0,0);
REP(i,0,adj[s].size())
{
if(farthest_dir[s][i]>best_dis.ff) {best_dis.ss=best_dis.ff; best_dis.ff=farthest_dir[s][i];}
else if(farthest_dir[s][i]>best_dis.ss) {best_dis.ss=farthest_dir[s][i];}
}
REP(i,0,adj[s].size())
{
if(adj[s][i]==p[s]) {continue;}
ll c = adj[s][i];
if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+val[c];}
else {farthest_up[c]=best_dis.ff+val[c];}
REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
}
REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
}
void Calc_farthest()
{
Calc_farthest_down(root);
Calc_farthest_up(root);
REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
}
};
Tree DFS_Tree(Graph G, ll s)
{
vector<ll> xx; REP(i,0,G.N) {G.dfs_tree.pb(xx);}
G.DFS_Tree(s);
Tree T(G.dfs_tree,s);
vector<vector<ll> > be; REP(i,0,T.N) {be.pb(xx);}
ll a,b,c;
REP(i,0,G.N)
{
REP(j,0,G.adj[i].size())
{
c = G.adj[i][j];
a=i; b=c;
if(a>b) {continue;}
if(T.level[a]>T.level[b]) {swap(a,b);}
if(T.p[b]!=a) {be[b].pb(a);}
}
}
T.Init_Back_Edge(be);
return T;
}
Tree Prufer(vector<ll> p) //constructs a Tree given unique Prufer code in O(N)
{
ll N=p.size()+2LL;
vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
ll ptr=0LL; vector<bool> v; REP(i,0,N) {v.pb(true);}
vector<ll> nadj; REP(i,0,N) {nadj.pb(1);}
REP(i,0,N-2) {nadj[p[i]]++;}
ll leaf; ll added=0LL;
while(added<N-2LL)
{
while(nadj[ptr]!=1LL && ptr<N) {ptr++;}
leaf=ptr;
while(leaf<=ptr && added<N-2LL)
{
v[leaf]=false; nadj[leaf]--; ll par=p[added]; nadj[par]--;
adj[leaf].pb(par); adj[par].pb(leaf);
added++;
if(nadj[par]>1) {break;}
leaf=par;
}
ptr++;
}
vector<ll> missing;
REP(i,0,N) {if(nadj[i]!=0LL) {missing.pb(i);}}
adj[missing[0]].pb(missing[1]); adj[missing[1]].pb(missing[0]);
Tree T(adj,0LL);
return T;
}
class WTree
{
public:
ll N;
vector<ll> p;
vector<vector<pl> > sons;
vector<vector<pl> > adj;
ll root;
vector<ll> level; //starting in 0
WTree(vector<vector<pl> > ad, ll r)
{
N=ad.size(); root=r; adj=ad;
vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0);}
DFS_Build(r,r);
}
void DFS_Build(ll s, ll par)
{
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i].ff,s);
}
return;
}
Tree Conv()
{
vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
vector<ll> values; REP(i,0,N) {values.pb(0LL);}
REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
Tree T(ad,root); T.val=values; T.DFS(T.root);
return T;
}
};
class WG //everything works for weighted directed graphs except dynamic graph
{
public:
ll N; vector<vector<pl> > adj;
vector<unordered_set<ll> > adjs; //for dynamic graph
unordered_map<pl,ll,hash_pair> we; //for dynamic graph
vector<bool> pr; vector<ll> nv;
vector<bool> deleted;
Matrix Madj;
WG(vector<vector<pl> > ad)
{
adj=ad; N=adj.size();
REP(i,0,N) {pr.pb(false); nv.pb(0);}
REP(i,0,N) {deleted.pb(false);}
unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); }
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
adjs[i].insert(adj[i][j].ff); we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
}
}
}
void Reset()
{
REP(i,0,N) {pr[i]=false;nv.pb(0);}
unordered_set<ll>::iterator it;
REP(i,0,N) {adj[i].clear(); it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(mp(*it,we[mp(i,*it)])); it++;}}
}
vector<ll> Djikstra(ll s)
{
Reset();
vector<ll> d; REP(i,0,N) {d.pb(INF);}
d[s]=0;
priority_queue<pl> q;
q.push(mp(0,s));
ll cur;
while(!q.empty())
{
cur=q.top().ss; q.pop();
if(pr[cur]) {continue;}
pr[cur]=true;
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
{
d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
}
}
}
return d;
}
vector<pl> Djikstra_MS(vector<ll> sn) //Djikstra Multi-sourced, ans[i].ff=d(i,sn), ans[i].ss=member of sn closest to i
{
Reset();
ll K=sn.size();
vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
priority_queue<pl> q;
REP(i,0,K) {q.push(mp(0,sn[i]));}
ll cur;
while(!q.empty())
{
cur=q.top().ss; q.pop();
if(pr[cur]) {continue;}
pr[cur]=true;
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
{
d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
d[adj[cur][i].ff].ss=d[cur].ss;
q.push(mp(-d[adj[cur][i].ff].ff,adj[cur][i].ff));
}
}
}
return d;
}
vector<ll> SPFA(ll s)
{
Reset();
vector<ll> d; REP(i,0,N) {d.pb(INF);}
d[s]=0;
deque<ll> tv; tv.pb(s); pr[s]=true;
ll cur; ll mv=0;
while(!tv.empty())
{
cur=tv.front(); tv.pop_front(); pr[cur]=false;
nv[cur]++; mv=max(mv,nv[cur]);
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
{
d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
pr[adj[cur][i].ff]=true;
}
}
if(mv>=N) {d.clear(); break;} //negative cycle
}
return d;
}
vector<pl> SPFA_MS(vector<ll> sn)
{
ll K=sn.size();
Reset();
vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
deque<ll> tv; REP(i,0,K) {tv.pb(sn[i]); pr[sn[i]]=true;}
ll cur; ll mv=0;
while(!tv.empty())
{
cur=tv.front(); tv.pop_front(); pr[cur]=false;
nv[cur]++; mv=max(mv,nv[cur]);
REP(i,0,adj[cur].size())
{
if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
{
d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
d[adj[cur][i].ff].ss=d[cur].ss;
if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
pr[adj[cur][i].ff]=true;
}
}
if(mv>=N) {d.clear(); break;} //negative cycle
}
return d;
}
vector<vector<ll> > Floyd() //assumes there is no neg cycle
{
Reset();
vector<vector<ll> > d; vector<ll> xx; REP(i,0,N) {xx.pb(INF);} REP(i,0,N) {d.pb(xx);}
REP(i,0,N)
{
d[i][i]=0;
REP(j,0,adj[i].size())
{
d[i][adj[i][j].ff]=adj[i][j].ss;
}
}
REP(i,0,N)
{
REP(q1,0,N)
{
REP(q2,0,N)
{
if(q1==q2) {continue;}
d[q1][q2]=min(d[q1][q2],d[q1][i]+d[i][q2]);
}
}
}
return d;
}
WTree Kruskal() //Minimum Spanning Tree, O(MlogM)
{
vector<pair<ll,pl> > ed; vector<vector<pl> > ad; vector<pl> xx; REP(i,0,N) {ad.pb(xx);}
pair<ll,pl> cur;
REP(i,0,N)
{
cur.ss.ff=i;
REP(j,0,adj[i].size())
{
cur.ss.ss=adj[i][j].ff;
cur.ff=adj[i][j].ss;
ed.pb(cur);
}
}
sort(ed.begin(),ed.end()); DSU D(N); ll a,b,we;
REP(i,0,ed.size())
{
a=ed[i].ss.ff; b=ed[i].ss.ss; we=ed[i].ff;
if(D.find(a)!=D.find(b))
{
D.unionn(a,b); ad[a].pb(mp(b,we)); ad[b].pb(mp(a,we));
}
}
WTree T(ad,0);
return T;
}
WTree Prim() //Minimim Spanning Tree, O(MlogM)
{
vector<vector<pl> > ad; vector<pl> xx; REP(i,0,N) {ad.pb(xx);}
vector<bool> inT; REP(i,0,N) {inT.pb(false);}
priority_queue<pair<pl,pl> > q;
q.push(mp(mp(0,0),mp(0,0))); ll s;
while(!q.empty())
{
s=q.top().ff.ss; pl bef=q.top().ss; q.pop();
if(inT[s]) {continue;}
inT[s]=true;
if(s!=0) {ad[s].pb(bef); ad[bef.ff].pb(mp(s,bef.ss));}
REP(i,0,adj[s].size())
{
if(inT[adj[s][i].ff]) {continue;}
q.push(mp(mp(-adj[s][i].ss,adj[s][i].ff),mp(s,adj[s][i].ss)));
}
}
WTree T(ad,0);
return T;
}
void erase_edge(pl edge)
{
adjs[edge.ff].erase(edge.ss); adjs[edge.ss].erase(edge.ff);
}
void add_edge(pair<pl,ll> edge)
{
if(adjs[edge.ff.ff].find(edge.ff.ss)==adjs[edge.ff.ff].end())
{
we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss);
we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss);
adjs[edge.ff.ff].insert(edge.ff.ss);
adjs[edge.ff.ss].insert(edge.ff.ff);
}
else
{
we[edge.ff]+=edge.ss; swap(edge.ff.ff,edge.ff.ss);
we[edge.ff]+=edge.ss;
}
}
void erase_node(ll s)
{
deleted[s]=true;
unordered_set<ll>::iterator it; it=adjs[s].begin(); vector<pl> e;
while(it!=adjs[s].end())
{
e.pb(mp(s,*it));
it++;
}
REP(i,0,e.size()) {erase_edge(e[i]);}
}
void add_node(vector<pl> con) // adds node with adjacency list con, and index N
{
N++; pr.pb(false); nv.pb(0); deleted.pb(false); unordered_set<ll> em; vector<pl> emm; adjs.pb(em); adj.pb(emm);
REP(i,0,con.size()) {add_edge(mp(mp(N-1,con[i].ff),con[i].ss));}
}
Matrix SMul(Matrix A, Matrix B)
{
if(A.M!=B.N) {Matrix ANS; return ANS;}
vector<double> xx; vector<vector<double> > ans; REP(i,0,B.M) {xx.pb((double) (INF));} REP(i,0,A.N) {ans.pb(xx);}
REP(i,0,A.N)
{
REP(j,0,B.M)
{
double val=(double) INF;
REP(k,0,A.M) {val=min(val,A.a[i][k]+B.a[k][j]);}
ans[i][j]=val;
}
}
Matrix ANS(ans); return ANS;
}
Matrix fastexpS(Matrix A, ll e) //O(N^3loge)
{
if(A.N!=A.M) {Matrix ANS; return ANS;}
if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexpS(*(A.Inv),-e);}}
if(e==0)
{Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=(double) INF;} else {ANS.a[i][j]=0.0;}}} return ANS;}
if(e%2LL==0)
{
Matrix V =fastexpS(A,(ll) e/2LL); return SMul(V,V);
}
else
{
Matrix V=fastexpS(A,(ll) e/2LL); return SMul(SMul(V,V),A);
}
}
void Build_Madj()
{
if(Madj.N!=0LL) {return;}
vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb((double) (INF));} REP(i,0,N) {madj.pb(xx);}
REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j].ff]=(double) (adj[i][j].ss);}}
Matrix B(madj); Madj=B;
}
double SP(ll a, ll b, ll length) //shortest path between a,b with fixed length, O(N^3loglength)
{
Build_Madj();
return (fastexpS(Madj,length).a[a][b]);
}
};
class DiGraph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited;
vector<ll> current; //for CC
vector<bool> c; //for Bip
bool bip; //for Bip
vector<ll> TS;//Top Sort
vector<ll> SCC; //Attributes a number to each node
vector<vector<ll> > adjK; //reverse graph, for Kosaraju
vector<unordered_set<ll> > adjs; vector<unordered_set<ll> > adjr; //dynamic graph
vector<bool> deleted; //dynamic graph
unordered_map<pair<vector<bool>,ll>,vector<ll>,hash_pair> mH; //Hamiltonian
vector<list<ll> > ad; //for Hierholzer
Matrix Madj;
DiGraph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
vector<ll> xx; REP(i,0,N) {adjK.pb(xx);}
REP(i,0,adj.size())
{
REP(j,0,adj[i].size()) {adjK[adj[i][j]].pb(i);}
}
unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); adjr.pb(em);}
REP(i,0,N)
{
REP(j,0,adj[i].size())
{
adjs[i].insert(adj[i][j]);
adjr[adj[i][j]].insert(i);
}
}
REP(i,0,N) {deleted.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
unordered_set<ll>::iterator it;
REP(i,0,N) {adj[i].clear();it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(*it); it++;}}
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
else if(c[adj[s][i]]==c[s]) {bip=false;}
}
current.pb(s); //only needed for Kosaraju
return;
}
vector<ll> BFS(ll s)
{
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i]])
{
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]]=distance[cur]+1;
}
}
}
return distance;
}
bool Bip()
{
c[0]=0;
bip=true;
DFS(0);
if(bip) {return true;}
else {return false;}
}
void DFSTS(ll s)
{
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {DFSTS(adj[s][i]);}
}
visited[s]=true; TS.pb(s);
}
void TopSort()
{
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFSTS(i);
}
reverse(TS.begin(),TS.end());
}
void DFSK(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adjK[s].size())
{
if(!visited[adjK[s][i]]) {DFSK(adjK[s][i]);}
}
current.pb(s); //only needed for Kosaraju
return;
}
void Kosaraju()
{
if(SCC[0]!=-1) {return;}
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFS(i);
}
vector<ll> List=current;
Reset();
ll c=0LL;
for(ll i=N-1LL;i>=0LL;i--)
{
ll node=List[i];
if(visited[node]) {continue;}
DFSK(node);
REP(j,0,current.size()) {SCC[current[j]]=c;}
c++;
current.clear();
}
}
DiGraph SCCGraph()
{
Kosaraju();
set<pl> ed;
REP(i,0,adj.size())
{
REP(j,0,adj[i].size())
{
ed.insert(mp(SCC[i],SCC[adj[i][j]]));
}
}
vector<vector<ll> > a; vector<ll> xx;
ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
REP(i,0,nscc) {a.pb(xx);}
set<pl>::iterator it=ed.begin();
pl cur;
while(it!=ed.end())
{
cur=*it;
if(cur.ff!=cur.ss) {a[cur.ff].pb(cur.ss);}
it++;
}
DiGraph ans(a);
return ans;
}
void erase_edge(pl edge)
{
adjs[edge.ff].erase(edge.ss);
adjr[edge.ss].erase(edge.ff);
}
void add_edge(pl edge)
{
adjs[edge.ff].insert(edge.ss);
adjr[edge.ss].insert(edge.ff);
adj[edge.ff].pb(edge.ss);
}
void erase_node(ll s)
{
deleted[s]=true;
unordered_set<ll>::iterator it; vector<pl> e;
if(adjs[s].size()>0) {it=adjs[s].begin(); while(it!=adjs[s].end()) {e.pb(mp(s,*it)); it++;}}
if(adjr[s].size()>0) {it=adjr[s].begin(); while(it!=adjr[s].end()) {e.pb(mp(*it,s)); it++;}}
REP(i,0,e.size()) {erase_edge(e[i]);}
}
void add_node(vector<ll> in, vector<ll> out) // adds node with adjacency list con, and index N
{
unordered_set<ll> em; adjs.pb(em); adjr.pb(em); vector<ll> emm; adj.pb(emm); deleted.pb(false); N++;
SCC.pb(-1);
REP(i,0,out.size()) {add_edge(mp(N-1,out[i]));}
REP(i,0,in.size()) {add_edge(mp(in[i],N-1));}
}
vector<ll> Hamiltonian()
{
vector<bool> v; REP(i,0,N) {v.pb(true);}
REP(i,0,N) {v[i]=true;}
REP(i,0,N)
{
if(!f(v,i).empty()) {return f(v,i);}
}
vector<ll> ans; return ans;
}
vector<ll> f(vector<bool> v, ll x) //O(N^2*2^N), for when we dont know anything about the graph
{
if(!mH[mp(v,x)].empty()) {return mH[mp(v,x)];}
ll oc=0LL; REP(i,0,N) {if(v[i]) {oc++;}}
vector<ll> ans;
if(oc==1) {ans.pb(x);}
else
{
v[x]=false; ll node;
REP(i,0,adjK[x].size())
{
node=adjK[x][i];
if(!v[node]) {continue;}
vector<ll> p=f(v,node);
if(!p.empty()) {p.pb(x); ans=p; break;}
}
}
mH[mp(v,x)]=ans;
return ans;
}
void Tour(ll s)
{
current.pb(s);
if(ad[s].size()==0) {return;}
ll nxt=*ad[s].begin(); ad[s].erase(ad[s].begin());
Tour(nxt);
}
vector<ll> Hierholzer() //O(M)
{
vector<ll> indeg; vector<ll> outdeg; REP(i,0,N) {indeg.pb(0LL); outdeg.pb(0LL);}
REP(i,0,N) {REP(j,0,adj[i].size()) {outdeg[i]++; indeg[adj[i][j]]++;}}
ll onep=0LL; ll onem=0LL; ll un=0LL;
REP(i,0,N)
{
if(outdeg[i]-indeg[i]==-1) {onem++;}
else if(outdeg[i]-indeg[i]==1) {onep++;}
else if(abs(outdeg[i]-indeg[i])>1) {un++;}
}
if(un!=0LL || onem>1LL || onep>1LL) {vector<ll> xxx; return xxx;}
ll sn=0LL; REP(i,0,N) {if(outdeg[i]-indeg[i]==1LL) {sn=i;}}
Reset(); DFS(sn); REP(i,0,N) {if(!visited[i]) {vector<ll> xxx; return xxx;}}
list<ll> ans;
list<ll> xx;
REP(i,0,N) {xx.clear(); xx.insert(xx.begin(),adj[i].begin(),adj[i].end()); ad.pb(xx);}
ans.insert(ans.begin(),sn);
list<ll>::iterator it=ans.begin();
REP(i,0,INF)
{
if(it==ans.end()) {break;}
current.clear();
Tour(*it);
it=ans.erase(it);
it=ans.insert(it,current.begin(),current.end());
it++;
}
it=ans.begin();
vector<ll> f_ans; REP(i,0,ans.size()) {f_ans.pb(*it); it++;}
return f_ans;
}
ll Edge_Disjoint(ll source, ll terminator) //max number of edge disjoint pahts source --> terminator
{
vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,N) {Wadj.pb(xx);}
REP(i,0,N)
{
REP(j,0,adj[i].size()) {Wadj[i].pb(mp(adj[i][j],1LL));}
}
WDiGraph G(Wadj);
return G.MF_Dinic(source,terminator);
}
ll Node_Disjoint(ll source, ll terminator) //max number of node disjoint paths source --> terminator
{
vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,2*N) {Wadj.pb(xx);}
REP(i,0,N)
{
Wadj[2*i].pb(mp(2*i+1,1));
REP(j,0,adj[i].size()) {Wadj[2*i+1].pb(mp(2*adj[i][j],1LL));}
}
WDiGraph G(Wadj);
return G.MF_Dinic(source,terminator);
}
ll Node_Disjoint_Path_Cover() //min number of node disjoint paths to cover all nodes in DAG, O(MN^1/2)
{
vector<vector<ll> > Uadj; vector<ll> xx; REP(i,0,2*N) {Uadj.pb(xx);}
REP(i,0,N)
{
REP(j,0,adj[i].size()) {Uadj[i].pb(adj[i][j]+N); Uadj[adj[i][j]+N].pb(i);}
}
Graph G(Uadj);
return (N-G.MaxMatching());
}
ll General_Path_Cover() //min number of paths to cover all nodes in DAG (situation in Dilworths Theorem), O(N^5/2 + NM)
{
vector<vector<ll> > Uadj; vector<ll> xx; REP(i,0,2*N) {Uadj.pb(xx);}
REP(i,0,N)
{
Reset(); DFS(i);
REP(j,0,N) {if(j==i || !visited[j]) {continue;} Uadj[i].pb(j+N); Uadj[j+N].pb(i);}
}
Graph G(Uadj);
return (N-G.MaxMatching());
}
void Build_Madj()
{
if(Madj.N!=0LL) {return;}
vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {madj.pb(xx);}
REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=1.0;}}
Matrix B(madj); Madj=B;
}
ll cnt_path(ll a, ll b, ll length)
{
Build_Madj();
return fastexp(Madj,length).a[a][b];
}
};
template<class T=ll>
class Heap
{
public:
ll N;
vector<T> a;
Heap() {N=0LL;}
Heap(vector<T> b) //O(N)
{
a=b; N=a.size(); ll cur;
REP(i,0,N)
{
cur=i;
while(cur>0LL && a[cur]>a[(cur-1)/2]) {swap(a[cur],a[(cur-1)/2]); cur=(cur-1)/2;}
}
}
void FixDown(ll node, T val) //a[node] -> val
{
a[node]=val; ll cur=node;
bool up=false;
if(node!=0 && a[node]>a[(node-1)/2]) {up=true;}
if(up)
{
while(cur>0 && a[cur]>a[(cur-1)/2]) {swap(a[cur],a[(cur-1)/2]); cur=(cur-1)/2;}
}
else
{
while(1>0)
{
if(2*cur+1<N && a[2*cur+1]>a[cur]) {swap(a[2*cur+1],a[cur]); cur=2*cur+1; continue;}
if(2*cur+2<N && a[2*cur+2]>a[cur]) {swap(a[2*cur+2],a[cur]); cur=2*cur+2; continue;}
break;
}
}
}
void addElement(T val)
{
a.pb(val); N++; FixDown(N-1,val);
}
};
ostream & operator << (ostream &out, Heap<ll> &H) {Out(H.a); return out;}
istream & operator >> (istream &in, Heap<ll> &H) {ll N; cin>>N; vector<ll> a; In(a,N); H.N=N; H.a=a; return in;}
template<class T=ll>
class AVL
{
public:
ll N;
class node
{
public:
T val;
ll h;
node *par;
node *lson, *rson;
node *prv,*nxt;
bool operator < (node A) {if(val<A.val) {return true;} return false;}
bool operator > (node A) {if(val>A.val) {return true;} return false;}
bool operator <= (node A) {if(val<=A.val) {return true;} return false;}
bool operator >= (node A) {if(val>=A.val) {return true;} return false;}
};
node * root, *beg, *en;
AVL()
{
en=(node *) malloc(sizeof(node));
en->lson=NULL; en->rson=NULL; en->par=NULL; en->h=0LL;
en->val=INF;
en->prv=NULL; en->nxt=NULL;
root=en; beg=en;
N=0LL;
}
node * begin() {return beg;}
node * end() {return en;}
node * find(T val)
{
node * cur = root;
while(1>0)
{
if(cur->val==val) {return cur;}
else if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
else if(cur->val < val && cur->rson != NULL) {cur=cur->rson;}
else {return en;}
}
}
node * lower_bound(T val)
{
node * cur = root; node * ans=root; ll mind=INF;
while(1>0)
{
if(cur->val==val) {return cur;}
if(cur->val >val && cur->val - val <mind) {mind=cur->val - val; ans=cur;}
if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
else if(cur->val < val && cur->rson != NULL) {cur=cur->rson;}
else {return ans;}
}
}
node * upper_bound(T val)
{
node * cur = root; node * ans=root; ll mind=INF;
while(1>0)
{
if(cur->val >val && cur->val - val <mind) {mind=cur->val - val; ans=cur;}
if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
else if(cur->val <= val && cur->rson != NULL) {cur=cur->rson;}
else {return ans;}
}
}
void Balance(node *X)
{
node * cur=X; bool balanced=true;
while(1>0)
{
ll h1=0, h2=0;
if(cur->lson!=NULL) {h1=cur->lson->h +1;}
if(cur->rson!=NULL) {h2=cur->rson->h +1;}
if(abs(h1-h2)>1) {balanced=false; break;}
if(cur==root) {break;}
cur=cur->par;
}
if(balanced) {return;}
ll h1=0; ll h2=0;
if(cur->lson!=NULL) {h1=cur->lson->h +1;}
if(cur->rson!=NULL) {h2=cur->rson->h +1;}
if(h2 > h1)
{
ll hl=0, hr=0;
if(cur->rson->lson!=NULL) {hl=cur->rson->lson->h +1;}
if(cur->rson->rson!=NULL) {hr=cur->rson->rson->h +1;}
if(hr>hl)
{
(cur->h)-=2;
node * A = cur->rson; if(cur->par==NULL) {root=A;}
A->par=cur->par; cur->par=A;
cur->rson=A->lson; if(A->lson!=NULL) {A->lson->par=cur;}
A->lson=cur;
if(A->par != NULL)
{
if(A->par->rson==cur) {A->par->rson=A;}
if(A->par->lson==cur) {A->par->lson=A;}
}
cur=A;
while(cur!=root)
{
cur=cur->par; (cur->h)--;
}
}
else
{
node * A = cur; node * B = A->rson; node * C = B->lson; node * D = C->lson; node * E = C->rson;
if(root==A) {root=C;}
C->par=A->par;
if(C->par != NULL)
{
if(C->par->rson==A) {C->par->rson=C;}
if(C->par->lson==A) {C->par->lson=C;}
}
A->par=C; C->lson=A;
A->rson=D; if(D!=NULL) {D->par=A;}
B->lson=E; if(E!=NULL) {E->par=B;}
B->par=C; C->rson=B;
B->h=0; if(B->rson!=NULL) {B->h=B->rson->h + 1;}
A->h=0; if(A->lson!=NULL) {A->h=A->lson->h + 1;}
(C->h)++;
cur=C;
while(cur!=root)
{
cur=cur->par; (cur->h)--;
}
}
}
else
{
ll hl=0, hr=0;
if(cur->lson->lson!=NULL) {hl=cur->lson->lson->h +1;}
if(cur->lson->rson!=NULL) {hr=cur->lson->rson->h +1;}
if(hl>hr)
{
(cur->h)-=2;
node * A = cur->lson; if(cur->par==NULL) {root=A;}
A->par=cur->par; cur->par=A;
cur->lson=A->rson; if(A->rson!=NULL) {A->rson->par=cur;}
A->rson=cur;
if(A->par != NULL)
{
if(A->par->rson==cur) {A->par->rson=A;}
if(A->par->lson==cur) {A->par->lson=A;}
}
cur=A;
while(cur!=root)
{
cur=cur->par; (cur->h)--;
}
}
else
{
node * A = cur; node * B = A->lson; node * C = B->rson; node * D = C->rson; node * E = C->lson;
if(root==A) {root=C;}
C->par=A->par; A->par=C; A->lson=D;
B->rson=E; B->par=C;
C->rson=A; C->lson=B;
if(D!=NULL) {D->par=A;}
if(E!=NULL) {E->par=B;}
B->h=0; if(B->lson!=NULL) {B->h=B->lson->h + 1;}
A->h=0; if(A->rson!=NULL) {A->h=A->rson->h + 1;}
(C->h)++;
if(C->par != NULL)
{
if(C->par->rson==cur) {C->par->rson=C;}
if(C->par->lson==cur) {C->par->lson=C;}
}
cur=C;
while(cur!=root)
{
cur=cur->par; (cur->h)--;
}
}
}
return;
}
void insert(T val)
{
node * next = lower_bound(val);
node * X = (node *) malloc(sizeof(node));
X->val=val; X->h=0; X->par=NULL; X->lson=NULL; X->rson=NULL;
node * cur=root;
N++;
while(cur->lson != NULL && cur->rson !=NULL)
{
(cur->h)++;
if(*cur>=*X) {cur=cur->lson;}
else {cur=cur->rson;}
}
(cur->h)++;
if(cur->lson==NULL && cur->rson==NULL)
{
if(*cur>=*X) {cur->lson=X; X->par=cur;}
else {cur->rson=X; X->par=cur;}
}
else if(cur->lson==NULL)
{
if(*cur>=*X) {cur->lson=X; X->par=cur;}
else
{
cur=cur->rson; (cur->h)++;
if(*X>=*cur) {cur->rson=X; X->par=cur;}
else {cur->lson=X; X->par=cur;}
}
}
else if(cur->rson==NULL)
{
if(*cur<=*X) {cur->rson=X; X->par=cur;}
else
{
cur=cur->lson; (cur->h)++;
if(*X>=*cur) {cur->rson=X; X->par=cur;}
else {cur->lson=X; X->par=cur;}
}
}
if(*X < *beg) {beg=X;}
Balance(X);
X->nxt=next; X->prv=(X->nxt->prv);
X->nxt->prv=X; if(X->prv !=NULL) {X->prv->nxt=X;}
}
void erase(node *X)
{
X->nxt->prv=X->prv;
if(X->prv!=NULL) {X->prv->nxt=X->nxt;}
if(X==beg) {beg=beg->nxt;}
if(X->lson==NULL && X->rson==NULL)
{
node * cur=X; node * p = cur->par;
cur->h=-1; cur=p;
while(1>0)
{
ll h1=0; ll h2=0;
if(cur->lson!=NULL) {h1=cur->lson->h +1;}
if(cur->rson!=NULL) {h2=cur->rson->h +1;}
cur->h=max(h1,h2);
if(cur==root) {break;}
cur=cur->par;
}
cur=X;
if((cur->par)->rson==cur) {(cur->par)->rson=NULL;}
if((cur->par)->lson==cur) {(cur->par)->lson=NULL;}
free(cur);
N--;
Balance(p);
return;
}
if(X->rson==NULL)
{
node * cur=X; node * p = cur->lson;
cur->h=-1; cur=p;
while(1>0)
{
ll h1=0; ll h2=0;
if(cur->lson!=NULL) {h1=cur->lson->h +1;}
if(cur->rson!=NULL) {h2=cur->rson->h +1;}
cur->h=max(h1,h2);
if(cur==root) {break;}
cur=cur->par;
}
cur=X;
if(X==root) {p->par=NULL; root=p; return;}
if((cur->par)->rson==cur) {(cur->par)->rson=p;}
if((cur->par)->lson==cur) {(cur->par)->lson=p;}
p->par=cur->par;
free(cur);
N--;
Balance(p);
return;
}
if(X->lson==NULL)
{
node * cur=X; node * p = cur->rson;
cur->h=-1; cur=p;
while(1>0)
{
ll h1=0; ll h2=0;
if(cur->lson!=NULL) {h1=cur->lson->h +1;}
if(cur->rson!=NULL) {h2=cur->rson->h +1;}
cur->h=max(h1,h2);
if(cur==root) {break;}
cur=cur->par;
}
cur=X;
if(X==root) {p->par=NULL; root=p; return;}
if((cur->par)->rson==cur) {(cur->par)->rson=p;}
if((cur->par)->lson==cur) {(cur->par)->lson=p;}
p->par=cur->par;
free(cur);
N--;
Balance(p);
return;
}
node * p = X->lson;
while(p->rson!=NULL) {p=p->rson;}
swap(X->val,p->val);
erase(p);
}
};
template<class T=ll>
class HashTable
{
public:
ll M; ll N;
class node
{
public:
T val;
bool visited;
node * nxt, *prv;
};
vector<node> a;
node * be, *en;
HashTable(ll m)
{
M=m; node X = *((node *) malloc(sizeof(node)));
REP(i,0,M) {a.pb(X);}
be=(node *) malloc(sizeof(node));
en=(node *) malloc(sizeof(node));
be->prv=NULL; be->nxt=en;
en->prv=be; en->nxt=NULL;
N=0;
}
node * begin() {return be;}
node * end() {return en;}
ll hash(ll i)
{
return (i%M);
}
void insert(T val)
{
ll ind=hash(val);
while(a[ind].visited)
{
if(a[ind].val==val) {return;}
ind=(ind+1)%M;
}
a[ind].visited=true; a[ind].val=val; N++;
a[ind].nxt=end(); a[ind].prv=en->prv; a[ind].prv->nxt=&a[ind]; en->prv=&a[ind];
if(N==1) {be=&a[ind]; return;}
}
node * find(T val)
{
ll ind=hash(val);
while(a[ind].visited)
{
if(a[ind].val==val) {return &a[ind];}
ind=(ind+1)%M;
}
return end();
}
void erase(node * X)
{
N--;
X->visited=false; X->val=0LL;
X->nxt->prv=X->prv;
if(X->prv !=NULL) {X->prv->nxt=X->nxt;}
if(be==X) {be=X->nxt;}
}
};
class Trie
{
public:
ll N;
vector<string> val; vector<char> c;
vector<ll> p;
vector<vector<ll> > sons;
unordered_set<string> a;
unordered_map<string,ll> pos;
Trie() {N=1; p.pb(0); val.pb(""); c.pb(' '); pos[""]=0; vector<ll> em; sons.pb(em);}
void insert(string s)
{
a.insert(s);
if(pos.find(s)!=pos.end()) {return;}
string t=""; ll node;
REP(i,0,s.size())
{
node=pos[t];
t+=s[i];
if(pos.find(t)==pos.end())
{
N++;vector<ll> em; sons.pb(em);
val.pb(t);c.pb(s[i]);
p.pb(node);
sons[node].pb(N-1);
pos[t]=N-1;
}
}
}
};
ll LIS(vector<ll> a) //Longest strictly Increasing Subsequence in O(NlogN)
{
vector<ll> dp; dp.pb(-INF);
vector<ll>::iterator it;
REP(i,0,a.size())
{
it=upper_bound(dp.begin(),dp.end(),a[i]);
if(it==dp.end()) {dp.pb(a[i]); continue;}
*it=a[i];
}
return dp.size()-1LL;
}
template<class T=string>
ll LCS_dp(ll i, ll j, vector<vector<ll> > &dp, T a, T b) //i means prefix s[0...i]
{
if(i==0) {if(a[0]==b[j]) {dp[i][j]=1;} else {dp[i][j]=0;}}
else if(j==0) {if(a[i]==b[0]) {dp[i][j]=1;} else {dp[i][j]=0;}}
else
{
if(a[i]==b[j]) {dp[i][j]=LCS_dp(i-1,j-1,dp,a,b)+1;}
else {dp[i][j]=max(LCS_dp(i-1,j,dp,a,b),LCS_dp(i,j-1,dp,a,b));}
}
return dp[i][j];
}
template<class T=string>
ll LCS(T a, T b)
{
vector<ll> xx; vector<vector<ll> > dp; REP(i,0,b.size()) {xx.pb(0);} REP(i,0,a.size()) {dp.pb(xx);}
return LCS_dp<T>(a.size()-1,b.size()-1, dp, a, b);
}
template<class T=string>
ll L_dist_dp(ll i, ll j, vector<vector<ll> > &dp, T a, T b) //i means prefix s[0...(i+1)]
{
if(i==0) {dp[i][j]=j;}
else if(j==0) {dp[i][j]=i;}
else
{
ll c = 1; if(a[i-1]==b[j-1]) {c=0;}
dp[i][j]=min(min(L_dist_dp(i-1,j,dp,a,b)+1,L_dist_dp(i,j-1,dp,a,b)+1),L_dist_dp(i-1,j-1,dp,a,b)+c);
}
return dp[i][j];
}
template<class T=string>
ll L_dist(T a, T b) //Levenshtein distance
{
vector<ll> xx; vector<vector<ll> > dp; REP(i,0,b.size()+1) {xx.pb(0LL);} REP(i,0,a.size()+1) {dp.pb(xx);}
return L_dist_dp(a.size(),b.size(),dp,a,b);
}
vector<ll> IC(ll k, vector<ll> a) //#strictly increasing subsequences of length k ending in each position
{
ll N=a.size();
unordered_map<ll,ll> m; set<ll> vals; REP(i,0,N) {vals.insert(a[i]);}
ll cnt=0LL; set<ll>::iterator it=vals.begin();
while(it!=vals.end()) {m[*it]=cnt; cnt++; it++;}
REP(i,0,N) {a[i]=m[a[i]];}
vector<ll> ans; REP(i,0,N) {ans.pb(0LL);}
if(k>N) {return ans;}
if(k==1) {REP(i,0,N) {ans[i]=1LL;} return ans;}
vector<ll> last=IC(k-1,a);
ST S(ans);
REP(i,0,N)
{
ST::LV X(last[i]);
S.update(X,a[i],a[i],1);
ans[i]=S.query(0,a[i]-1LL,1).a;
}
return ans;
}
template<class T=string>
ll subcnt(T a, T b) //#subsequences of a that are equal to b (can be upgraded if occorrence of each value in b is restricted)
{
ll N=a.size(); ll M=b.size();
if(M>N) {return 0LL;}
vector<ll> oc; REP(i,0,M) {oc.pb(0LL);}
REP(i,0,N)
{
REP(j,0,M)
{
if(a[i]==b[j])
{
if(j==0) {oc[0]++;}
else {oc[j]+=oc[j-1];}
}
}
}
return oc[M-1];
}
vector<ModInt> PrefixHash(string s, ll B) //char a = 1, b = 2, ...
{
ll oldmod=mod;
mod=B;
ModInt cur=0; ll val; ModInt x=1;
vector<ModInt> ans;
REP(i,0,s.size())
{
val=(ll) (s[i]-'a'); val++;
cur+=(x*val);
x*=26LL;
ans.pb(cur);
}
mod=oldmod;
return ans;
}
template<class T=string>
vector<ll> ZArr(T s)
{
vector<ll> ans; REP(i,0,s.size()) {ans.pb(0);}
ans[0]=s.size(); ll x=1,y=1;
REP(i,1,s.size())
{
y=max(y,i);
if(y==i)
{
ll ind=0;
while(i+ind<s.size() && s[ind]==s[i+ind]) {ind++;}
ans[i]=ind;
y=i+ind;
x=i;
}
else if(i+ans[i-x]-1<=y-2)
{
ans[i]=ans[i-x];
}
else
{
ll ind=0;
while(y+ind<s.size() && s[y+ind]==s[y+ind-i]) {ind++;}
y=y+ind; x=i;
ans[i]=y-i;
}
}
return ans;
}
template<class T=string>
ll patt(T s, T p) //#substrings of s equal to p, O(N)
{
if(p.size()>s.size()) {return 0;}
T x=p; x+=' '; x+=s;
vector<ll> a=ZArr(x);
ll ans=0LL;
REP(i,p.size()+1,a.size())
{
if(a[i]==p.size()) {ans++;}
}
return ans;
}
vector<ll> SuffixArr(string s)
{
ll N = s.size();
unordered_map<char,ll> m1; ll curi=1LL;
set<char> used; REP(i,0,N) {used.insert(s[i]);}
set<char>::iterator it=used.begin();
while(it!=used.end())
{
m1[*it]=curi; curi++;
it++;
}
vector<ll> l,nl; REP(i,0,N) {l.pb(m1[s[i]]);nl.pb(0);}
ll si = 2LL;
set<pl> old; pl cur;
set<pl>::iterator ite;
unordered_map<pl,ll,hash_pair> m;
while(si<=N)
{
old.clear();
m.clear();
REP(i,0,N)
{
cur.ff=l[i]; if(i+si/2<N) {cur.ss=l[i+si/2];} else {cur.ss=0;}
old.insert(cur);
}
ite=old.begin();
curi=1LL;
while(ite!=old.end())
{
m[*ite]=curi; curi++;
ite++;
}
REP(i,0,N)
{
cur.ff=l[i]; if(i+si/2<N) {cur.ss=l[i+si/2];} else {cur.ss=0;}
nl[i]=m[cur];
}
l=nl;
si=2*si;
}
REP(i,0,N) {l[i]--;}
vector<ll> ans; REP(i,0,N) {ans.pb(0);}
REP(i,0,N) {ans[l[i]]=i;}
return ans;
}
vector<ll> LCPArr(string s, vector<ll> SuffixArr)
{
ll N = s.size();
vector<ll> pos; vector<ll> LCP; REP(i,0,N) {pos.pb(0); LCP.pb(0);}
REP(i,0,N) {pos[SuffixArr[i]]=i;}
ll las = 0LL;
REP(i,0,N)
{
ll s1 = i; ll s2;
if(pos[i]+1<N) {s2 = SuffixArr[pos[i]+1];}
else {LCP[pos[i]]=0; las=0; continue;}
ll val=max(0LL,las-1LL);
while(s1+val<N && s2+val<N && s[s1+val]==s[s2+val]) {val++;}
LCP[pos[i]]=val;
las=val;
}
return LCP;
}
template<class T=ll>
T kSmall(vector<T> a, ll K) // K in [0,N-1], O(N)
{
if(a.size()<=50LL) {sort(a.begin(),a.end(),cmp<T>); return a[K];}
srand(time(NULL)*time(NULL));
ll x,y,z; x=rand()%a.size(); y=rand()%a.size(); z=rand()%a.size();
vector<T> dummy; dummy.pb(a[x]); dummy.pb(a[y]); dummy.pb(a[z]); sort(whole(dummy),cmp<T>);
T pivot=dummy[1LL];
vector<ll> rel; REP(i,0,a.size()) {rel.pb(0LL);}
ll sm=0LL; ll eq=0LL; ll bi=0LL;
REP(i,0,a.size())
{
if(a[i]<pivot) {rel[i]=-1;sm++;}
else if(a[i]>pivot) {rel[i]=1;bi++;}
else {rel[i]=0;eq++;}
}
if(sm<=K && sm+eq>=K+1LL) {return pivot;}
vector<T> nxt;
if(sm>=K+1LL) {REP(i,0,a.size()) {if(rel[i]==-1) {nxt.pb(a[i]);}} return kSmall(nxt,K);}
else {REP(i,0,a.size()) {if(rel[i]==1) {nxt.pb(a[i]);}} return kSmall(nxt,K-sm-eq);}
}
class LinRecursion //Linear Recursion
{
public:
ll K;
vector<double> c; //a_N = c1*a_N-1 + ... + cK*a_N-K
Matrix X; //Recursion Matrix
Matrix V0; //Initial vector
LinRecursion(vector<double> coef, vector<double> v0)
{
K=coef.size(); c=coef; vector<vector<double> > xxx; xxx.pb(v0); xxx.pb(v0); Matrix INSIG(xxx);
V0=~INSIG;
xxx.clear(); v0.clear(); REP(i,0,K) {v0.pb(0.0);} REP(i,0,K) {xxx.pb(v0);}
REP(i,0,K-1) {xxx[i][i+1]=1.0;}
REP(i,0,K) {xxx[K-1][i]=c[K-i-1];}
Matrix Y(xxx); X=Y;
}
double query(ll pos) //what's a_pos, pos from 0
{
return ((fastexp(X,pos)*V0).a[0][0]);
}
};
vector<bool> SAT2(ll N, vector<pl> a)
{
ll M=a.size();
vector<vector<ll> > adj; vector<ll> xx; REP(i,0,2*N) {adj.pb(xx);}
pl c;
REP(i,0,M)
{
if(a[i].ff==-a[i].ss) {continue;}
c.ff = -a[i].ff; c.ss=a[i].ss;
if(c.ff<0) {c.ff=2*(-c.ff)-1;}
else {c.ff=2*c.ff-2;}
if(c.ss<0) {c.ss=2*(-c.ss)-1;}
else {c.ss=2*c.ss-2;}
adj[c.ff].pb(c.ss);
swap(a[i].ff,a[i].ss);
c.ff = -a[i].ff; c.ss=a[i].ss;
if(c.ff<0) {c.ff=2*(-c.ff)-1;}
else {c.ff=2*c.ff-2;}
if(c.ss<0) {c.ss=2*(-c.ss)-1;}
else {c.ss=2*c.ss-2;}
adj[c.ff].pb(c.ss);
}
DiGraph G(adj); G.Kosaraju();
vector<bool> ans; REP(i,0,N) {if(G.SCC[2*i]==G.SCC[2*i+1]) {return ans;}}
REP(i,0,N)
{
if(G.SCC[2*i]>G.SCC[2*i+1]) {ans.pb(true);}
else {ans.pb(false);}
}
return ans;
}
vector<vector<ll> > Sum_Set_Cover(vector<vector<ll> > p, ll MAX) //given vectors p0,...,pk-1, is it possible to get sum S in [0,MAX-1] by choosing exactly one element in each vector? ans[i][S] is -1 if S is not attainable in i steps (p0,...,pi), else it is e, meaning the chosen element in pi was pi[e]. pi[j] must be non-negative. Variation of Knapsack. O(MAX*max{pi.size()})
{
vector<vector<ll> > ans; vector<ll> em; REP(i,0,MAX) {em.pb(-1);} REP(i,0,p.size()) {ans.pb(em);}
REP(i,0,p.size())
{
if(i==0)
{
REP(j,0,p[0].size())
{
if(p[0][j]>=MAX) {continue;}
ans[0][p[0][j]]=j;
}
continue;
}
REP(j,0,MAX)
{
if(ans[i-1][j]==-1) {continue;}
REP(z,0,p[i].size())
{
if(j+p[i][z]>=MAX) {continue;}
ans[i][j+p[i][z]]=z;
}
}
}
return ans;
}
bool cmpMo(pl a, pl b)
{
pl p1,p2;
p1.ff=a.ff/Mo_bucket; p1.ss=a.ss;
p2.ff=b.ff/Mo_bucket; p2.ss=b.ss;
return (p1<p2);
}
class Sym //Symmetric sum
{
public:
ll N;
vector<pair<ll,vector<ll> > > c;
Sym() {}
Sym(ll n) {N=n;}
Sym(vector<ll> coef) {N=coef.size(); c.pb(mp(1LL,coef));}
vector<ll> perm; vector<vector<ll> > perms;
void Perm(unordered_multiset<ll> left)
{
if(left.empty())
{
perms.pb(perm);
}
else
{
unordered_multiset<ll> copy = left;
unordered_multiset<ll>::iterator it=left.begin();
while(it!=left.end())
{
perm.pb(*it); copy.erase(copy.find(*it));
Perm(copy);
perm.pop_back(); copy.insert(*it);
it++;
}
}
}
Sym operator *(ll k)
{
Sym ANS=(*this);
REP(i,0,ANS.c.size()) {ANS.c[i].ff*=k;}
ANS.zip();
return ANS;
}
Sym operator + (Sym X)
{
Sym ANS = (*this);
REP(i,0,X.c.size()) {ANS.c.pb(X.c[i]);}
ANS.zip();
return ANS;
}
Sym operator * (Sym X)
{
Sym ANS(N);
REP(a,0,c.size())
{
unordered_multiset<ll> s;
REP(i,0,N) {s.insert(c[a].ss[i]);}
Perm(s);
REP(b,0,X.c.size())
{
REP(i,0,perms.size())
{
vector<ll> cur; REP(z,0,N) {cur.pb(perms[i][z]+X.c[b].ss[z]);}
ANS.c.pb(mp(c[a].ff*X.c[b].ff,cur));
}
}
perms.clear();
}
ANS.zip();
return ANS;
}
void zip()
{
REP(i,0,c.size()) {sort(whole(c[i].ss)); reverse(whole(c[i].ss));}
set<pair<vector<ll>,ll> > s; set<pair<vector<ll>,ll> >::iterator it;
REP(i,0,c.size())
{
it=s.lower_bound(mp(c[i].ss,-INF));
if(it==s.end()) {s.insert(mp(c[i].ss,c[i].ff));}
else if(it->ff==c[i].ss) {pair<vector<ll>,ll> p; p.ff=it->ff; p.ss=it->ss+c[i].ff; s.erase(it); s.insert(p);}
else {s.insert(mp(c[i].ss,c[i].ff));}
}
c.clear();
it=s.begin();
while(it!=s.end())
{
c.pb(mp(it->ss,it->ff));
it++;
}
reverse(whole(c));
}
void disp()
{
zip();
REP(i,0,c.size()) {cout<<c[i].ff<<" * ( "; REP(j,0,c[i].ss.size()) {cout<<c[i].ss[j]<<" ";} cout<<")"<<endl;}
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
return 0;
}
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 11:03:25 (j3).
Desktop version, switch to mobile version.
Supported by
