#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//多项式全家桶
namespace polynomial{
const int maxn=1<<20,mod=998244353;
int mo(const int x){
return x>=mod?x-mod:x;
}
int power(int a,int x){
int re=1;
while(x){
if(x&1)re=1ll*re*a%mod;
a=1ll*a*a%mod,x>>=1;
}
return re;
}
const int g_=3;
int rev[maxn],gN[maxn];
void initNTT(int m,int&n){
n=1;int cn=-1;
while(n<m)n<<=1,++cn;
gN[0]=1;gN[1]=power(g_,(mod-1)/n);
for(int i=1;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<cn),
gN[i]=1ll*gN[i-1]*gN[1]%mod;
}
void NTT(int*F,int n,int rv){
for(int i=0;i<n;++i)if(rev[i]<i)
F[i]^=F[rev[i]]^=F[i]^=F[rev[i]];
for(int mid=1;mid<n;mid<<=1){
const int len=mid<<1,gn=n/len;
for(int i=0;i<n;i+=len){
for(int j=0,g=0;j<mid;++j,g+=gn){
int l=i+j,r=l+mid;
int L=F[l],R=1ll*F[r]*gN[g]%mod;
F[l]=mo(L+R),F[r]=mo(mod-R+L);
}
}
}
if(!rv)return;std::reverse(F+1,F+n);int I=mod-(mod-1)/n;
for(int i=0;i<n;++i)F[i]=1ll*F[i]*I%mod;
}
int Inv[maxn];
void inv(int*F,int*G,int n){
//G(x)=inv(F(x)) mod x^n;
if(n==1)return G[0]=power(F[0],mod-2),void();
inv(F,G,(n+1)>>1);for(int i=(n+1)>>1;i<n;++i)G[i]=0;
int cp=n;initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)Inv[i]=F[i];for(int i=cp;i<n;++i)Inv[i]=G[i]=0;
NTT(Inv,n,0);NTT(G,n,0);for(int i=0;i<n;++i)
G[i]=1ll*G[i]*mo(mod-1ll*G[i]*Inv[i]%mod+2)%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Ln[maxn];
void ln(int*F,int*G,int n){
//G(x)=ln(F(x)) mod x^n;
for(int i=0;i<n;++i)Ln[i]=0;
inv(F,Ln,n);int cp=n;
initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)G[i]=1ll*F[i+1]*(i+1)%mod;
for(int i=cp;i<n;++i)G[i]=Ln[i]=0;NTT(G,n,0);NTT(Ln,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Ln[i]%mod;NTT(G,n,1);
for(int i=cp-1;i>=1;--i)G[i]=1ll*G[i-1]*power(i,mod-2)%mod;
G[0]=0;for(int i=cp;i<n;++i)G[i]=0;
}
int Exp[maxn];
void exp(int*F,int*G,int n){
//G(x)=exp(F(x)) mod x^n;
if(n==1)return G[0]=1,void();exp(F,G,(n+1)>>1);
for(int i=(n+1)>>1;i<n;++i)G[i]=0;
for(int i=0;i<n;++i)Exp[i]=0;ln(G,Exp,n);
for(int i=0;i<n;++i)Exp[i]=mo(mod-Exp[i]+F[i]+(i==0));
int cp=n;initNTT((n+1)*2,n);
for(int i=cp;i<n;++i)Exp[i]=G[i]=0;NTT(G,n,0);NTT(Exp,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Exp[i]%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Power[maxn];
void power(int*F,int*G,int n,int m0,int m1,int m2){
//G(x)=power(F(x),m) mod x^n;
//m0=m%mod m1=m%(mod-1) m2=stand for m
int no=0;while(no<n&&F[no]==0)++no;
if(1ll*no*m2>=n){for(int i=0;i<n;++i)G[i]=0;return;}
int V=F[no],I=power(V,mod-2);
for(int i=0;i+no<n;++i)G[i]=1ll*F[i+no]*I%mod,Power[i]=0;
for(int i=n-no;i<n;++i)G[i]=Power[i]=0;ln(G,Power,n);
for(int i=0;i<n;++i)Power[i]=1ll*Power[i]*m0%mod;
exp(Power,G,n);V=power(V,m1);no*=m2;
for(int i=n-1;i>=no;--i)G[i]=1ll*G[i-no]*V%mod;
for(int i=no-1;i>=0;--i)G[i]=0;
}
int Divide0[maxn],Divide1[maxn];
void divide(int*F,int*G,int*Q,int*R,int n,int m){
//F(x)=Q(x)G(x)+R(x) Q(x)? R(x)? deg(F)=n-1 deg(G)=m-1
int tn=n-m+1;
for(int i=0;i<tn;++i)Divide1[i]=(m>=i+1?G[m-i-1]:0);
inv(Divide1,Divide0,tn);
for(int i=0;i<tn;++i)Divide1[i]=(n>=i+1?F[n-i-1]:0);
int cp=tn;initNTT((n+1)*2,tn);
NTT(Divide0,tn,0);NTT(Divide1,tn,0);
for(int i=0;i<tn;++i)Q[i]=1ll*Divide0[i]*Divide1[i]%mod;
NTT(Q,tn,1);for(int i=cp;i<tn;++i)Q[i]=0;std::reverse(Q,Q+cp);
for(int i=0;i<tn;++i)Divide0[i]=Q[i],Divide1[i]=G[i];
NTT(Divide0,tn,0);NTT(Divide1,tn,0);
for(int i=0;i<tn;++i)R[i]=1ll*Divide0[i]*Divide1[i]%mod;
NTT(R,tn,1);for(int i=0;i<tn;++i)R[i]=mo(mod-R[i]+F[i]);
}
}
//平衡树
namespace Treap{
const int maxn=100005;
struct Node{
int l,r,sz,val;
Node(int l=0,int r=0,int sz=0,int val=0):
l(l),r(r),sz(sz),val(val){}
}P[maxn];
int tot;
void pushup(int x){
P[x].sz=P[P[x].l].sz+P[P[x].r].sz+1;
}
void pushdown(int x){
//
}
int build(int val){
P[++tot]=Node(0,0,1,val);return tot;
}
//left_size=k
void split_size(int x,int&l,int&r,int k){
if(!x)return l=r=0,void();
pushdown(x);int o=P[P[x].l].sz+1;
if(k>=o)l=x,split_size(P[x].r,P[l].r,r,k-o);
else r=x,split_size(P[x].l,l,P[r].l,k);
pushup(x);
}
//left_val<=v
void split_value(int x,int&l,int&r,int v){
if(!x)return l=r=0,void();
pushdown(x);int o=P[x].val;
if(v>=o)l=x,split_value(P[x].r,P[l].r,r,v);
else r=x,split_value(P[x].l,l,P[r].l,v);
pushup(x);
}
int rd(int l,int r){
return 1ll*rand()*(l+r)<1ll*RAND_MAX*l;
}
void merge_tree(int&x,int l,int r){
if(!l||!r)return x=l|r,void();
pushdown(x);
if(rd(P[l].sz,P[r].sz))x=l,merge_tree(P[x].r,P[l].r,r);
else x=r,merge_tree(P[x].l,l,P[r].l);
pushup(x);
}
int root;
void ins(int val){
int x,y;
split_value(root,x,y,val);
merge_tree(x,x,build(val));
merge_tree(root,x,y);
}
void del(int val){
int x,y,z;
split_value(root,x,y,val-1);
split_value(y,y,z,val);
merge_tree(y,P[y].l,P[y].r);
merge_tree(y,y,z);
merge_tree(root,x,y);
}
int rank(int val){
int x,y;
split_value(root,x,y,val-1);
int ans=P[x].sz+1;
merge_tree(root,x,y);
return ans;
}
int knar(int sz,int&rt=root){
int x,y,z;
split_size(rt,x,y,sz-1);
split_size(y,y,z,1);
int ans=P[y].val;
merge_tree(y,y,z);
merge_tree(rt,x,y);
return ans;
}
//max_val<val
int lower(int val){
int x,y,z;
split_value(root,y,z,val-1);
split_size(y,x,y,P[y].sz-1);
int ans=P[y].val;
merge_tree(y,x,y);
merge_tree(root,y,z);
return ans;
}
//min_val>val
int upper(int val){
int x,y,z;
split_value(root,x,y,val);
split_size(y,y,z,1);
int ans=P[y].val;
merge_tree(y,y,z);
merge_tree(root,x,y);
return ans;
}
void print(int x){
if(!x)return;
putchar('(');print(P[x].l);
printf("%d ",P[x].val);
print(P[x].r);putchar(')');
}
}
namespace Splay{
const int maxn=100005;
#define root P[0].s[0]
struct Node{
int s[2],p,sz,val;
Node(int l=0,int r=0,int p=0,int sz=0,int val=0){
this->s[0]=l,this->s[1]=r;
this->p=p,this->sz=sz,this->val=val;
}
}P[maxn];
int tot;
void pushup(int x){
P[x].sz=P[P[x].s[0]].sz+P[P[x].s[1]].sz+1;
}
void pushdown(int x){
//
}
int identify(int x){
return P[P[x].p].s[1]==x;
}
void connect(int p,int x,int t){
P[p].s[t]=x;if(x)P[x].p=p;
}
void rotate(int x){
int o=identify(x),p=P[x].p;
connect(p,P[x].s[!o],o);
connect(P[p].p,x,identify(p));
connect(x,p,!o);
pushup(p);pushup(x);
}
//keep splay, so the information can always be updated.
void splay(int st,int ed){
ed=P[ed].p;
while(P[st].p!=ed){
int up=P[st].p;
if(P[up].p!=ed){
if(identify(up)==identify(st))
rotate(up);
else
rotate(st);
}
rotate(st);
}
}
int build(int val,int pa){
P[++tot]=Node(0,0,pa,1,val);
return tot;
}
//splay val to the root
void find(int val){
int x=root;
while(x){
pushdown(x);
if(P[x].val==val)
return splay(x,root);
int t=P[x].val<val;
x=P[x].s[t];
}
}
void ins(int val){
if(!root)
root=build(val,0);
else{
int x=root;
while(x){
pushdown(x);
int t=P[x].val<val;
if(!P[x].s[t]){
splay(P[x].s[t]=build(val,x),root);
return;
}
x=P[x].s[t];
}
}
}
void del(int val){
find(val);
if(!P[root].s[0])
connect(0,P[root].s[1],0);
else{
int x=P[root].s[0];
while(P[x].s[1]){
pushdown(x);
x=P[x].s[1];
}
pushdown(x);
splay(x,P[root].s[0]);
connect(P[root].s[0],P[root].s[1],1);
pushup(P[root].s[0]);
connect(0,P[root].s[0],0);
}
}
int rank(int val){
int ans=1;
int x=root;
while(x){
pushdown(x);
int t=P[x].val<val;
if(t)ans+=P[P[x].s[0]].sz+1;
if(!P[x].s[t]){
splay(x,root);
x=0;
}
else
x=P[x].s[t];
}
return ans;
}
int knar(int sz){
int x=root;
while(x){
pushdown(x);
int o=P[P[x].s[0]].sz+1;
if(o==sz){
splay(x,root);
return P[x].val;
}
if(sz>o)
sz-=o,x=P[x].s[1];
else
x=P[x].s[0];
}
return 0;
}
#define inf 0x3f3f3f3f
int lower(int val){
int x=root,ans=-inf;
while(x){
pushdown(x);
int t=P[x].val<val;
if(t)ans=P[x].val;
if(!P[x].s[t]){
splay(x,root);x=0;
}
else x=P[x].s[t];
}
return ans;
}
int upper(int val){
int x=root,ans=inf;
while(x){
pushdown(x);
int t=P[x].val<=val;
if(!t)ans=P[x].val;
if(!P[x].s[t]){
splay(x,root);x=0;
}
else x=P[x].s[t];
}
return ans;
}
#undef inf
}
//动态树
namespace LinkCutTree{
const int maxn=100005;
struct Node{
int s[2],p,val,rv,sm;
//rv 用来维护换根操作
//这里 sm 举例求路径异或和
Node(int l=0,int r=0,int p=0,int val=0,int rv=0,int sm=0){
this->s[0]=l,this->s[1]=r;this->p=p;
this->val=val,this->rv=rv,this->sm=sm;
}
}P[maxn];
void push(int x){
if(x){
std::swap(P[x].s[0],P[x].s[1]);
P[x].rv^=true;
}
}
void pushdown(int x){
if(!P[x].rv)return;P[x].rv=false;
push(P[x].s[0]);push(P[x].s[1]);
}
void pushup(int x){
P[x].sm=P[P[x].s[0]].sm^P[P[x].s[1]].sm^P[x].val;
}
bool isroot(int x){
return P[P[x].p].s[0]!=x&&P[P[x].p].s[1]!=x;
}
int identify(int x){
return P[P[x].p].s[1]==x;
}
void connect(int p,int x,int t){
P[p].s[t]=x;if(x)P[x].p=p;
}
void rotate(int x){
int o=identify(x),p=P[x].p;
connect(p,P[x].s[!o],o);
if(isroot(p))P[x].p=P[p].p;
else connect(P[p].p,x,identify(p));
connect(x,p,!o);
pushup(p);pushup(x);
}
//just splay x to the root
int st[maxn];
void splay(int x){
//remember to pushdown!
int tp=0;
while(!isroot(x))
st[++tp]=x,x=P[x].p;
st[++tp]=x;
while(tp)pushdown(st[tp--]);
x=st[1];
while(!isroot(x)){
int p=P[x].p;
if(!isroot(p)){
if(identify(p)==identify(x))
rotate(p);
else
rotate(x);
}
rotate(x);
}
}
void access(int x){
//make x access to the real root
for(int y=0;x;y=x,x=P[x].p){
splay(x);P[x].s[1]=y;pushup(x);
}
}
void makeroot(int x){
access(x);splay(x);push(x);
}
//split the path x-?-y
void split(int x,int y){
makeroot(x);access(y);splay(y);
}
int ask(int x,int y){
split(x,y);return P[y].sm;
}
void modify(int x,int val){
access(x);splay(x);
P[x].val=val;pushup(x);
}
void link(int x,int y){
split(x,y);
//only if x and y are unconnected
if(!P[x].p)P[x].p=y;
}
void cut(int x,int y){
split(x,y);
//only if the edge (x,y) exists
if(P[y].s[0]==x){
P[x].p=P[y].s[0]=0;
pushup(y);
}
}
}
//图论算法
//最短路
namespace ShortestPath{
const int maxn=100005,maxm=200005;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm];
int num,hd[maxn];
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]);hd[u]=num;
}
struct Val{
int v;long long w;
Val(int v=0,long long w=0):
v(v),w(w){}
bool operator < (const Val o)const{
return w>o.w;
}
};
long long dis[maxn];
std::priority_queue<Val>q;
void dijkstra_heap(int s){
memset(dis,0x3f,sizeof dis);
q.push(Val(s,dis[s]=0));
while(!q.empty()){
Val tmp=q.top();q.pop();
if(tmp.w!=dis[tmp.v])continue;
int u=tmp.v;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
q.push(Val(v,dis[v]=dis[u]+w));
}
}
}
}
#define inf 0x3f3f3f3f3f3f3f3fll
int lock[maxn];
void dijkstra(int s,int n){
memset(dis,0x3f,sizeof dis);
memset(lock,0,sizeof lock);
dis[s]=0;
for(int i=1;i<=n;++i){
long long mv=inf;int u=0;
for(int j=1;j<=n;++j){
if(!lock[j]&&dis[j]<mv){
mv=dis[u=j];
}
}
lock[u]=true;
for(int j=hd[u];j;j=e[j].nt){
int v=e[j].v,w=e[j].w;
if(dis[v]>dis[u]+w)
dis[v]=dis[u]+w;
}
}
}
#undef inf
}
//K短路
namespace KShortestPath{
const int maxn=100005,maxm=200005;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm];
int num,hd[maxn];
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]);hd[u]=num;
}
struct Val{
int v;long long w;
Val(int v=0,long long w=0):
v(v),w(w){}
bool operator < (const Val o)const{
return w>o.w;
}
};
long long dis[maxn];
int st[maxn],tp=0;
std::priority_queue<Val>q;
void dijkstra(int s){
memset(dis,0x3f,sizeof dis);
q.push(Val(s,dis[s]=0));
while(!q.empty()){
Val tmp=q.top();q.pop();
if(tmp.w!=dis[tmp.v])continue;
int u=st[++tp]=tmp.v;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
q.push(Val(v,dis[v]=dis[u]+w));
}
}
}
}
struct Node{
int l,r,dis;Val v;
Node(int l=0,int r=0,int dis=0,Val v=Val()):
l(l),r(r),dis(dis),v(v){}
}P[maxm+maxn*18];
int tot;
void update(int x){
if(P[P[x].l].dis<P[P[x].r].dis){
std::swap(P[x].l,P[x].r);
P[x].dis=P[P[x].r].dis+1;
}
}
void ins(int&x,Val v){
if(!x){
P[++tot]=Node(0,0,1,v);x=tot;
return;
}
if(P[x].v<v){
P[++tot]=Node(x,0,1,v);x=tot;
return;
}
ins(P[x].l,v);
update(x);
}
void merge(int&x,int l,int r){
if(!l||!r)return x=l|r,void();
if(P[l].v<P[r].v)std::swap(l,r);
x=++tot;P[x]=P[l];
merge(P[x].r,P[l].r,r);
update(x);
}
#define inf 0x3f3f3f3f3f3f3f3fll
int rt[maxn],pre[maxn];
long long solve(int s,int t,int k,int n){
dijkstra(s);
if(k==1)return dis[t];
for(int u=1;u<=n;++u){
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[u]>=inf)continue;
if(!pre[v]&&dis[v]==dis[u]+w)pre[v]=u;
else ins(rt[v],Val(u,dis[u]+w-dis[v]));
}
}
for(int i=2;i<=tp;++i){
int u=st[i];
merge(rt[u],rt[u],rt[pre[u]]);
}
if(rt[t]){
q.push(Val(rt[t],P[rt[t]].v.w));
}
long long ans=0;
while((k--)&&!q.empty()){
Val tmp=q.top();q.pop();int node=tmp.v;ans=tmp.w;
if(P[node].l)q.push(Val(P[node].l,ans-P[node].v.w+P[P[node].l].v.w));
if(P[node].r)q.push(Val(P[node].r,ans-P[node].v.w+P[P[node].r].v.w));
if(rt[P[node].v.v])q.push(Val(rt[P[node].v.v],ans+P[rt[P[node].v.v]].v.w));
}
if(k==-1)return ans+dis[t];
else return inf;
}
#undef inf
}
//有向图强连通分量
//Strongly Connected Component
namespace SCC{
const int maxn=100005,maxm=200005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm],e2[maxm];
//Kosaraju 要存反图
int num,hd[maxn];
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
e2[num]=Edge(u,hd[v]),hd[v]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],in[maxn],tp;
int scn,sc[maxn];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
in[st[++tp]=u]=true;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=std::min(low[u],low[v]);
}
else if(in[v])
low[u]=std::min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
//These vertice form a scc
++scn;
while(st[tp]!=u){
in[st[tp]]=false;
sc[st[tp]]=scn;
--tp;
}
in[st[tp--]]=false;
sc[u]=scn;
}
}
void solve_tarjan(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i);
}
void kosaraju1(int u){
dfn[u]=true;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(dfn[v])continue;
kosaraju1(v);
}
st[dfn[u]=++tp]=u;
}
void kosaraju2(int u){
sc[u]=scn;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(sc[v])continue;
kosaraju2(v);
}
}
void solve_kosaraju(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])kosaraju1(i);
for(int i=n;i>=1;--i)
if(!sc[st[i]])++scn,kosaraju2(st[i]);
}
}
//无向图点双连通分量
//Point Biconnected Component
namespace PBC{
const int maxn=100005,maxm=200005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm*2];
int hd[maxn],num;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],tp;
//注意栈中最后还会剩一个元素
void tarjan(int u){
dfn[u]=low[u]=++cnt;st[++tp]=u;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=std::min(low[u],low[v]);
if(low[v]==dfn[u]){
//These vertice with u form a pbc or an edge
while(st[tp]!=v){
--tp;
}
--tp;
}
}
else low[u]=std::min(low[u],dfn[v]);
}
}
void solve(int n){
for(int i=1;i<=n;++i){
if(!dfn[i])tarjan(i),--tp;
}
}
}
//无向图边双连通分量
//Edge Biconnected Component
namespace EBC{
const int maxn=500005,maxm=2000005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm*2];
int hd[maxn],num=1;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],tp;
void tarjan(int u,int te){
dfn[u]=low[u]=++cnt;st[++tp]=u;
for(int i=hd[u];i;i=e[i].nt){
if(i==te)continue;
//remember to delete the tree-edge
int v=e[i].v;
if(!dfn[v]){
tarjan(v,i^1);
low[u]=std::min(low[u],low[v]);
}
else low[u]=std::min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
//These vertice form an ebc or just a point
while(st[tp]!=u){
--tp;
}
--tp;
}
}
void solve(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i,0);
}
}
//网络流
namespace Dinic{
const int maxn=205,maxm=5005;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm*2];
int hd[maxn],num=1;
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]);hd[u]=num;
e[++num]=Edge(u,0,hd[v]);hd[v]=num;
}
int n,S,T,q[maxn],dis[maxn];
int bfs(void){
//n编号最大
for(int i=1;i<=n;++i)dis[i]=0;
int fro=0,bac=0;
dis[q[bac++]=S]=1;
while(fro<bac){
int u=q[fro++];
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(w&&!dis[v])dis[q[bac++]=v]=dis[u]+1;
}
}
return dis[T];
}
int cur[maxn];
long long dfs(int u,long long lef){
if(u==T)return lef;long long re=0;
for(int&i=cur[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(w&&dis[v]==dis[u]+1){
int tmp=dfs(v,w<lef?w:lef);
e[i].w-=tmp,e[i^1].w+=tmp;
lef-=tmp,re+=tmp;
if(!lef)break;
}
}
return re;
}
#define inf 0x3f3f3f3f
long long dinic(void){
long long max_flow=0;
while(bfs()){
for(int i=1;i<=n;++i)cur[i]=hd[i];
max_flow+=dfs(S,inf);
}
return max_flow;
}
#undef inf
}
//费用流
namespace MCMF_SPFA{
const int maxn=5005,maxm=50005;
struct Edge{
int v,w,f,nt;
Edge(int v=0,int w=0,int f=0,int nt=0):
v(v),w(w),f(f),nt(nt){}
}e[maxm*2];
int hd[maxn],num=1;
void qwq(int u,int v,int w,int f){
e[++num]=Edge(v,w,f,hd[u]),hd[u]=num;
e[++num]=Edge(u,0,-f,hd[v]),hd[v]=num;
}
int n,S,T;
int in[maxn],q[maxn];
int dis[maxn],flow[maxn],pre[maxn];
#define inf 0x3f3f3f3f
int spfa(void){
for(int i=1;i<=n;++i)
flow[i]=0,dis[i]=inf,pre[i]=0;
int fro=0,bac=0;
q[bac++]=S;
dis[S]=0;
flow[S]=inf;
while(fro!=bac){
int u=q[fro++];if(fro==maxn)fro=0;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w,f=e[i].f;
if(w&&dis[v]>dis[u]+f){
pre[v]=i;dis[v]=dis[u]+f;
flow[v]=std::min(flow[u],w);
if(!in[v]){
in[q[bac++]=v]=true;
if(bac==maxn)bac=0;
}
}
}
in[u]=false;
}
return flow[T];
}
void solve(void){
int max_flow=0,min_cost=0;
while(spfa()){
max_flow+=flow[T];
min_cost+=flow[T]*dis[T];
int x=T;
while(x){
e[pre[x]].w-=flow[T];
e[pre[x]^1].w+=flow[T];
x=e[pre[x]^1].v;
}
}
}
}
//PS:这个 dijkstra 不一定是正优化
namespace MCMF_dijkstra{
const int maxn=5005,maxm=50005;
struct Edge{
int v,w,f,nt;
Edge(int v=0,int w=0,int f=0,int nt=0):
v(v),w(w),f(f),nt(nt){}
}e[maxm*2];
int hd[maxn],num=1;
void qwq(int u,int v,int w,int f){
e[++num]=Edge(v,w,f,hd[u]),hd[u]=num;
e[++num]=Edge(u,0,-f,hd[v]),hd[v]=num;
}
int n,S,T;
int in[maxn],q[maxn];
int h[maxn],dis[maxn],flow[maxn],pre[maxn];
#define inf 0x3f3f3f3f
void spfa(void){
for(int i=1;i<=n;++i)h[i]=inf;
int fro=0,bac=0;
q[bac++]=S;h[S]=0;
while(fro!=bac){
int u=q[fro++];if(fro==maxn)fro=0;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w,f=e[i].f;
if(w&&h[v]>h[u]+f){
h[v]=h[u]+f;
if(!in[v]){
in[q[bac++]=v]=true;
if(bac==maxn)bac=0;
}
}
}
in[u]=false;
}
}
struct Val{
int v,w;
Val(int v=0,int w=0):
v(v),w(w){}
bool operator < (const Val o)const{
return w>o.w;
}
};
std::priority_queue<Val>hp;
#define inf 0x3f3f3f3f
int dijkstra(void){
for(int i=1;i<=n;++i)
dis[i]=inf,flow[i]=pre[i]=0;
hp.push(Val(S,dis[S]=0));flow[S]=inf;
while(!hp.empty()){
Val tmp=hp.top();hp.pop();
int u=tmp.v;if(tmp.w!=dis[u])continue;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w,f=e[i].f;
if(w&&dis[v]>dis[u]-h[v]+h[u]+f){
hp.push(Val(v,dis[v]=dis[u]-h[v]+h[u]+f));
flow[v]=std::min(flow[u],w);pre[v]=i;
}
}
}
return flow[T];
}
#undef inf
void solve(void){
int max_flow=0,min_cost=0;
spfa();
while(dijkstra()){
max_flow+=flow[T];
min_cost+=flow[T]*(dis[T]+h[T]);
int x=T;
while(x){
e[pre[x]].w-=flow[T];
e[pre[x]^1].w+=flow[T];
x=e[pre[x]^1].v;
}
for(int i=1;i<=n;++i)h[i]=dis[i];
}
printf("%d %d\n",max_flow,min_cost);
}
}
//最小树形图
//Directed Minimum Spanning Tree
namespace DMST{
const int maxn=100005,maxm=200005;
struct Val{
int v,w;
Val(int v=0,int w=0):
v(v),w(w){}
Val operator += (const int o){
this->w=this->w+o;return *this;
}
bool operator < (const Val o)const{
return w<o.w;
}
};
struct Node{
int l,r,dis,laz;Val v;
Node(int l=0,int r=0,int dis=0,int laz=0,Val v=Val()):
l(l),r(r),dis(dis),laz(laz),v(v){}
}P[maxm];
int tot;
void push(int x,int laz){
P[x].laz+=laz;
P[x].v+=laz;
}
void pushdown(int x){
if(!P[x].laz)return;
push(P[x].l,P[x].laz);
push(P[x].r,P[x].laz);
P[x].laz=0;
}
void pushup(int x){
if(P[P[x].l].dis<P[P[x].r].dis)
std::swap(P[x].l,P[x].r);
P[x].dis=P[P[x].r].dis+1;
}
int newnode(Val v){
P[++tot]=Node(0,0,1,0,v);
return tot;
}
void merge(int&x,int l,int r){
if(!l||!r)return x=l|r,void();
pushdown(l);pushdown(r);
if(P[r].v<P[l].v)l^=r^=l^=r;
x=l;merge(P[x].r,P[l].r,r);
return pushup(x);
}
void pop(int&x){
pushdown(x);
merge(x,P[x].l,P[x].r);
}
int rt[maxn];
int id[maxn];
int vis[maxn],cnt;
int st[maxn],tp;
int find(int x){
return id[x]==x?x:id[x]=find(id[x]);
}
#define inf 0x3f3f3f3f
int dfs(int u){
if(vis[u]&&vis[u]<cnt)return 0;
if(vis[u]==cnt){
while(st[tp]!=u){
id[st[tp]]=u;
merge(rt[u],rt[u],rt[st[tp]]);
--tp;
}
}
else vis[u]=cnt,st[++tp]=u;
if(rt[u]==0)return -inf;
Val tmp=P[rt[u]].v;
pop(rt[u]);push(rt[u],-tmp.w);
return tmp.w+dfs(find(tmp.v));
}
#undef inf
//由于不用存图，这里直接输入了
int solve(void){
int n,m,r;
scanf("%d%d%d",&n,&m,&r);
//所有点要都可以到达 r
vis[r]=cnt=1;
for(int i=1;i<=n;++i)
id[i]=i;
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
merge(rt[v],rt[v],newnode(Val(u,w)));
}
int ans=0;
for(int i=1;i<=n;++i){
if(i!=r&&!vis[i]){
++cnt;
int tmp=dfs(i);tp=0;
if(tmp<0)return -1;//无解
ans+=tmp;
}
}
return ans;
}
}
//KMP
namespace KMP{
const int maxn=100005;
int next[maxn];
void getnext(char*s){
int n=strlen(s+1);
next[1]=0;
for(int i=2;i<=n;++i){
int j=next[i-1];
while(j&&s[j+1]!=s[i])j=next[j];
if(s[j+1]==s[i])next[i]=j+1;
else next[i]=0;
}
}
void KMP(char*s1,char*s2){
//Find s2 in s1
getnext(s2);
int n=strlen(s1+1),
m=strlen(s2+1);
int i=1,j=1;
while(i<=n){
while(j>1&&s1[i]!=s2[j])
j=next[j-1]+1;
if(s1[i]==s2[j]){
++i;++j;
if(j==m+1){
//Find it!
printf("%d\n",i-m);
j=next[j-1]+1;
}
}
else ++i;
}
for(int i=1;i<=m;++i)
printf("%d%c",next[i]," \n"[i==m]);
}
}
//ACAM
namespace ACAM{
const int maxn=100005;
int son[maxn][26],fail[maxn],tot;
int newnode(void){
++tot;memset(son[tot],0,sizeof son[tot]);
fail[tot]=0;return tot;
}
void ins(char*s){
int n=strlen(s+1),now=0;
for(int i=1;i<=n;++i){
int o=s[i]-'a';
if(!son[now][o])
son[now][o]=newnode();
now=son[now][o];
}
}
int q[maxn];
void build(void){
int fro=0,bac=0;
for(int i=0;i<26;++i)if(son[0][i])
fail[q[bac++]=son[0][i]]=0;
while(fro<bac){
int u=q[fro++];
for(int i=0;i<26;++i){
if(son[u][i])
fail[q[bac++]=son[u][i]]=son[fail[u]][i];
//else son[u][i]=son[fail[u][i]];
}
}
}
}
//SA 后缀数组
namespace SA{
const int maxn=1000005;
int rk[maxn],sa[maxn];
void solve(char*s){
int n=strlen(s+1);
}
}
int main(){
return 0;
}
原文链接: https://www.cnblogs.com/lsq147/p/17020033.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/309251
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
