1 /* // 图论模板 // */
2 //-----------------------------------------------------------------------------
3 /*卡常小技巧*/
4 #define re register
5 #define max(x,y) ((x)>(y)?(x):(y))
6 #define min(x,y) ((x)<(y)?(x):(y))
7 #define swap(x,y) ((x)^=(y)^=(x)^=(y))
8 #define abs(x) ((x)<0?-(x):(x))
9 inline + 函数（非递归）
10 static 相当于全局变量，防止爆栈，且不用重复申请空间，初值为0
11 //-----------------------------------------------------------------------------
12 /*前向星邻接表*/
13 //单向链表
14 int tot,first[100010];
15 struct node{int u,v,w,next;}edge[200010];
16 inline void add(re int x,re int y,re int w){
17 edge[++tot].u=x;
18 edge[tot].v=y;
19 edge[tot].w=w;
20 edge[tot].next=first[x];
21 first[x]=tot;
22 }
23 //双向链表
24 int tot,head[100010],tail[100010];
25 struct node{int u,v,next,last;}edge[200010];
26 inline void add(re int x,re int y){
27 edge[++tot].u=x;
28 edge[tot].v=y;
29 edge[tot].w=w;
30 edge[tot].next=0;
31 edge[tot].last=tail[x];
32 edge[tail[x]].next=tot;tail[x]=tot;
33 if(!head[x]) head[x]=tot;
34 }
35 //-----------------------------------------------------------------------------
36 /*遍历（dfs，bfs)*/
37 //dfs
38 void dfs(re int x,re int fa){
39 for(re int i=first[x];i;i=edge[i].next){
40 re int y=edge[i].v;
41 if(y==fa) continue;
42 dfs(y,x);
43 }
44 }
45 //bfs
46 inline void bfs(re int s){
47 static queue<int> q;
48 q.push(s);ins[s]=1;
49 while(!q.empty()){
50 re int x=q.front();q.pop(),ins[x]=0;
51 for(re int i=first[x];i;i=edge[i].next){
52 re int y=edge[i].v;
53 if(ins[y]) continue;
54 q.push(y);ins[y]=1;
55 }
56 }
57 }
58 //-----------------------------------------------------------------------------
59 /*最短路*/
60 //Floyd
61 for(re int k=1;k<=n;++k)
62 for(re int i=1;i<=n;++i)
63 for(re int j=1;j<=n;++j)
64 if(f[i][k]+f[k][j]<f[i][j])
65 f[i][j]=f[i][k]+f[k][j];
66 //堆优化Dijkstra
67 inline void Dijkstra(re int s){
68 static priority_queue<pair<int,int> > q;
69 memset(dis,0x3f,sizeof(dis));dis[s]=0;
70 q.push(make_pair(dis[s],s));
71 while(!q.empty()){
72 re int x=q.top();q.pop();
73 if(vis[x]) continue;vis[x]=1;
74 for(re int i=first[x];i;i=edge[i].next){
75 re int y=edge[i].v,w=edge[i].w;
76 if(dis[x]+w<dis[y]){
77 dis[y]=dis[x]+w;
78 q.push(make_pair(dis[y],y));
79 }
80 }
81 }
82 }
83 //spfa
84 inline void spfa(re int s){
85 static queue<int> q;
86 memset(dis,0x3f,sizeof(dis));
87 dis[s]=0;q.push(s);ins[s]=1;
88 while(!q.empty()){
89 re int x=q.front();q.pop();ins[x]=0;
90 for(re int i=first[x];i;i=edge[i].next){
91 re int y=edge[i].v,w=edge[i].w;
92 if(dis[x]+w<dis[y]){
93 dis[y]=dis[x]+w;
94 if(!ins[y]) q.push(y),ins[y]=1;
95 }
96 }
97 }
98 }
99 //-----------------------------------------------------------------------------
100 /*拓扑排序*/
101 inline void topsort(){
102 static queue<int> q;
103 for(re int i=1;i<=n;++i)
104 if(!in[i]) q.push(i);
105 while(!q.empty()){
106 re int x=q.front();q.pop();
107 for(re int i=first[x];i;i=edge[i].next){
108 re int y=edge[i].v; --in[y];
109 if(!in[y]) q.push(y);
110 }
111 }
112 }
113 //-----------------------------------------------------------------------------
114 /*并查集*/
115 //普通并查集
116 int find(re int x){return fa[x]==x?x:find(fa[x]);}
117 inline void merge(re int x,re int y){
118 x=find(x),y=find(y);
119 if(x!=y) fa[x]=y;
120 }
121 //路径压缩
122 int find(re int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
123 //按秩合并
124 inline void merge(re int x,re int y){
125 x=find(x),y=find(y);
126 if(x==y) return ;
127 if(rk[x]<=rk[y]) fa[x]=y,rk[y]=max(rk[y],rk[x]+1);
128 else fa[y]=x,rk[x]=max(rk[x],rk[y]+1);
129 }
130 //-----------------------------------------------------------------------------
131 /*最小生成树*/
132 //Kruskal
133 inline bool cmp(node x,node y){
134 return x.w<y.w;
135 }
136 inline void Kruskal(){
137 sort(a+1,a+m+1,cmp);
138 for(re int i=1;i<=m;i++){
139 re int x=a[i].x,y=a[i].y;
140 x=find(x),y=find(y);
141 if(x==y) continue;
142 fa[x]=y,++cnt,ans+=a[i].w;
143 if(cnt==n-1) break;
144 }
145 }
146 //prim
147 inline void init(){
148 for(re int i=1;i<=n;++i)
149 for(re int j=1;j<=n;++j)
150 w[i][j]=inf;
151 for(re int i=1,u,v,w;i<=m;++i){
152 u=read(),v=read(),w=read();
153 if(w[u][v]>w) w[u][v]=w[v][u]=w;
154 }
155 for(re int i=1;i<=n;++i) to[i]=w[1][i];
156 fm[1]=1;
157 }
158 inline int prim(){
159 while(tot<n){
160 re int minn=inf,now;++tot;
161 for(re int i=1;i<=n;++i)
162 if(!fm[i]&&to[i]<minn)minn=to[i],now=i;
163 ans+=minn;
164 for(re int i=1;i<=n;++i)
165 if(to[i]>w[now][i]&&!fm[i]) to[i]=w[now][i];
166 fm[now]=1;
167 }
168 return ans;
169 }
170 //-----------------------------------------------------------------------------
171 /*树的直径*/
172 //树形DP
173 void dfs(re int x){
174 vis[x]=1;
175 for(re int i=first[x];i;i=edge[i].next){
176 re int y=edge[i].v;if(vis[y]) continue;
177 dfs(y);ans=max(ans,dep[x]+dep[y]+edge[i].w);
178 dep[x]=max(dep[x],dep[y]+edge[i].w);
179 }
180 }
181 //两遍dfs
182 void dfs(re int x,re int fa){
183 for(re int i=first[x];i;i=edge[i].next){
184 re int y=edge[i].v;
185 if(y==fa) continue;
186 dis[y]=dis[x]+1,pre[y]=x; dfs(y,x);
187 }
188 }
189 re int st=0,ed=0,len=0;
190 dis[1]=0;dfs(1,0);
191 for(re int i=1;i<=n;++i)
192 if(dis[i]>dis[st]) st=i;
193 dis[st]=0;dfs(st,0);
194 for(re int i=1;i<=n;++i)
195 if(dis[i]>dis[ed]) len=dis[ed],ed=i;
196 //-----------------------------------------------------------------------------
197 /*tarjan*/
198 //有向图强联通分量+缩点重建
199 void tarjan(re int x){
200 dfn[x]=low[x]=++cnt;
201 stk[++top]=x,ins[x]=1;
202 for(re int i=first[x];i;i=edge[i].next){
203 re int y=edge[i].v;
204 if(!dfn[y]){
205 tarjan(y);
206 low[x]=min(low[x],low[y]);
207 }
208 else if(ins[y]) low[x]=min(low[x],dfn[y]);
209 }
210 if(dfn[x]==low[x]){
211 ++cnt;re int dat;
212 do{
213 dat=stk[top--],ins[dat]=0;
214 bel[y]=cnt,scc[cnt].push_back(dat);
215 }while(dat!=x);
216 }
217 }
218 for(re int i=1;i<=n;++i)
219 if(!dfn[i]) tarjan(i);
220 for(re int x=1;x<=n;++x){
221 for(re int i=first[x];i;i=edge[i].next){
222 re int y=edge[i].v;
223 if(bel[x]==bel[y]) continue;
224 readd(bel[x],bel[y]);
225 }
226 }
227 //割点(无向图）
228 void tarjan(re int x){
229 dfn[x]=low[x]=++cnt;re int flag=0;
230 for(re int i=first[x];i;i=edge[i].next){
231 re int y=edge[i].v;
232 if(!dfn[y]){
233 tarjan(y);
234 low[x]=min(low[x],low[y]);
235 if(low[y]>=dfn[x]) {
236 ++flag;
237 if(x!=root||flag>1) cut[x]=1;
238 }
239 }
240 else low[x]=min(low[x],dfn[y]);
241 }
242 }
243 for(re int i=1;i<=n;++i)
244 if(!dfn[i]) root=i,tarjan(i);
245 //割边(无向图）
246 void tarjan(re int x,re int ed){
247 dfn[x]=low[x]=++cnt;
248 for(re int i=first[x];i;i=edge[i].next){
249 re int y=edge[i].v;
250 if(dfn[y]){
251 if(i!=(ed^1))
252 low[x]=min(low[x],dfn[y]);
253 continue;
254 }
255 tarjan(y,i);
256 low[x]=min(low[x],low[y]);
257 if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=1;
258 }
259 }
260 for(re int i=1;i<=n;++i)
261 if(!dfn[i]) tarjan(i,0);
262 //点双+缩点重建
263 void tarjan(re int x){
264 dfn[x]=low[x]=++num;
265 stk[++top]=x;
266 if(x==root&&first[x]==0){
267 dcc[++cnt].push_back(x);
268 return ;
269 }
270 re int flag=0;
271 for(re int i=first[x];i;i=edge[i].next){
272 re int y=edge[i].v;
273 if(!dfn[y]){
274 tarjan(y);
275 low[x]=min(low[x],low[y]);
276 if(low[y]>=dfn[x]){
277 ++flag;
278 if(x!=root||flag>1) cut[x]=1;
279 cnt++;re int dat;
280 do{
281 dat=stk[top--];
282 dcc[cnt].push_back(dat);
283 }while(dat!=y);
284 dcc[cnt].push_back(x);
285 }
286 }
287 else low[x]=min(low[x],dfn[y]);
288 }
289 }
290 for(re int i=1;i<=n;++i)
291 if(!dfn[i]) root=i,tarjan(i);
292 num=cnt;
293 for(re int i=1;i<=n;++i)
294 if(cut[i]) id[i]=++num;
295 retot=1;
296 for(re int i=1;i<=cnt;++i){
297 for(re int j=0;j<dcc[i].size();++j){
298 re int x=dcc[i][j];
299 if(cut[x])
300 readd(i,id[x]),readd(id[x],i);
301 else bel[x]=i;
302 }
303 }
304 //边双(即删除割边)(无向图)+缩点重建
305 void tarjan(re int x,re int ed){
306 dfn[x]=low[x]=++cnt;
307 for(re int i=first[x];i;i=edge[i].next){
308 re int y=edge[i].v;
309 if(dfn[y]){
310 if(i!=(ed^1))
311 low[x]=min(low[x],dfn[y]);
312 continue;
313 }
314 tarjan(y,i);
315 low[x]=min(low[x],low[y]);
316 if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=1;
317 }
318 }
319 void dfs(re int x){
320 id[x]=dcc;
321 for(re int i=first[x];i;i=edge[i].next){
322 re int y=edge[i].v;
323 if(id[y]||bridge[i]) continue;
324 dfs(y);
325 }
326 }
327 for(re int i=1;i<=n;++i)
328 if(!dfn[i]) tarjan(i,0);
329 for(re int i=1;i<=n;++i){
330 if(!id[i]) ++dcc,dfs(i);
331 }
332 for(re int i=1;i<=tot;++i){
333 re int x=edge[i].v,y=edge[i^1].v;
334 if(id[x]==id[y]) continue;
335 readd(id[x],id[y]);
336 }
337 //-----------------------------------------------------------------------------
338 /*二分图*/
339 //匈牙利算法（增广路算法）
340 bool dfs(re int x){
341 for(re int i=first[x];i;i=edge[i].next){
342 re int y=edge[i].v;
343 if(!vis[y]){
344 vis[y]=1;
345 if(!match[y]||dfs(match[y])){
346 match[y]=x;return 1;
347 }
348 }
349 }
350 return 0;
351 }
352 for(re int i=1;i<=n;++i){
353 memset(vis,0,sizeof(vis));
354 if(dfs(i)) ++ans;
355 }
356 //-----------------------------------------------------------------------------
357 /*lca*/
358 //倍增lca
359 void dfs(re int x,re int fa){
360 dep[x]=dep[fa]+1;
361 for(re int i=1;i<=20;++i)
362 f[x][i]=f[f[x][i-1]][i-1];
363 for(re int i=first[x];i;i=edge[i].next){
364 re int y=edge[i].v;
365 if(y==fa) continue;
366 f[y][0]=x;dfs(y,x);
367 }
368 }
369 inline int lca(re int x,re int y){
370 if(dep[x]<dep[y]) x^=y^=x^=y;
371 re int dat=dep[x]-dep[y];
372 for(re int i=0;i<=20;++i) if(dat>>i&1) x=f[x][i];
373 if(x==y) return x;
374 for(re int i=20;~i;--i)
375 if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
376 return f[x][0];
377 }
378 //ST表lca
379 void dfs(re int x,re int fa){
380 dep[x]=dep[fa]+1,id[x]=++cnt,euler[cnt]=x;
381 for(re int i=first[x];i;i=edge[i].next){
382 re int y=edge[i].v;
383 if(y==fa) continue;
384 dfs(y,x),euler[++cnt]=x;
385 }
386 }
387 inline void ST(){
388 for(re int i=1;i<=cnt;++i) f[i][0]=euler[i];
389 for(re int j=1;j<20;++j){
390 for(re int i=1;i<=cnt;++i){
391 if(i+(1<<j)>cnt) break;
392 if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]])
393 f[i][j]=f[i][j-1];
394 else f[i][j]=f[i+(1<<(j-1))][j-1];
395 }
396 }
397 }
398 inline int lca(re int x,re int y){
399 if(x>y) x^=y^=x^=y;
400 re int pos=(int)(log(y-x+1)/log(2));
401 re int res=f[x][pos];
402 re int k=f[y-(1<<pos)+1][pos];
403 if(dep[res]>dep[k]) res=k; return res;
404 }
405 LCA(x,y)=lca(id[x],id[y]);
406 //树链剖分lca
407 void dfs1(re int x){
408 siz[x]++;
409 for(re int i=first[x];i;i=edge[i].next){
410 re int y=edge[i].v;
411 if(dep[y]) continue;
412 dep[y]=dep[x]+1,fa[y]=x;
413 dfs1(y);siz[x]+=siz[y];
414 }
415 }
416 void dfs2(re int x,re int pt){
417 top[x]=pt;re int sz=0,pos=0;
418 for(re int i=first[x];i;i=edge[i].next){
419 re int y=edge[i].v;
420 if(fa[y]==x) continue;
421 if(siz[y]>sz)
422 pos=y,sz=siz[y];
423 }
424 dfs2(pos,pt);
425 for(re int i=first[x];i;i=edge[i].next){
426 re int y=edge[i].v;
427 if(y==pos||fa[y]==x) continue;
428 dfs2(y,y);
429 }
430 }
431 inline int lca(re int x,re int y){
432 while(top[x]!=top[y]){
433 if(dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
434 x=fa[top[x]];
435 }
436 return dep[x]<dep[y]?x:y;
437 }
438 //-----------------------------------------------------------------------------
439 /*欧拉回路*/
440 inline void euler(){
441 stk[++top]=1;
442 while(top){
443 re int x=stk[top],i=first[x];
444 while(i&&vis[i]) i=edge[i].next;
445 if(i){
446 stk[++top]=edge[i].v;
447 vis[i]=vis[i^1]=1;
448 first[x]=edge[i].next;
449 }
450 else top--,ans[++cnt]=x;
451 }
452 }
453 for(re int i=cnt;i;--i) printf("%d ",ans[i]);
454 //-----------------------------------------------------------------------------
455 /*网络流*/
456 //最大流EK
457 int tot=1;//!!!
458 struct node{int u,v,next,w,c,eg}edge[200010];//w:流量 c:容量
459 inline void add(re int x,re int y,re int w){
460 edge[tot]=(node){x,y,first[x],0,w,cnt+1};
461 first[x]=tot++;
462 edge[tot]=(node){y,x,first[y],0,0,cnt-1};
463 first[y]=tot++;
464 }
465 inline void EK(){
466 re int ans=0;static queue<int> q;
467 while(1){
468 for(re int i=1;i<=n;++i) a[i]=0;
469 while(!q.empty()) q.pop();
470 q.push(S);pre[S]=0;a[S]=inf;
471 while(!q.empty()){
472 re int x=q.front();q.pop();
473 for(re int i=first[x];i;i=edge[i].next){
474 re int y=edge[i].v;
475 if(!a[y]&&edge[i].c>edge[i].w){
476 a[y]=min(a[x],edge[i].c-edge[i].w);
477 pre[y]=i,q.push(y);
478 }
479 }
480 if(a[T]) break;
481 }
482 if(!a[T]) break;
483 for(re int u=T;u!=S;u=edge[pre[u]].u){
484 edge[pre[u]].w+=a[T];
485 edge[edge[pre[u]].eg].w-=a[T];
486 }
487 ans+=a[T];
488 }
489 }
490 //最大流dinic
491 int tot=1;//!!!
492 struct node{int v,next,w,eg}edge[200010];
493 inline void add(re int x,re int y,re int w){
494 edge[tot]=(node){x,y,first[x],w,cnt+1};
495 first[x]=tot++;
496 edge[tot]=(node){y,x,first[y],0,cnt-1};
497 first[y]=tot++;
498 }
499 inline bool bfs(){
500 for(re int i=1;i<=n;++i) bel[i]=0;
501 bel[S]=1;static queue<int> q;
502 while(!q.empty()) q.pop();
503 q.push(S);
504 while(!q.empty()){
505 re int x=q.front();q.pop();
506 for(re int i=first[x];i;i=edge[i].next){
507 re int y=edge[i].v;
508 if(edge[i].w&&!bel[y])
509 bel[y]=bel[x]+1,q.push(y);
510 }
511 }
512 return bel[T];
513 }
514 int dfs(re int s,re int t,re int flow){
515 if(s==t||flow==0) return flow;
516 re int res=0;
517 for(re int i=first[u];i;i=edge[i].next){
518 re int y=edge[i].v;
519 if(edge[i].w&&bel[y]==bel[u]+1){
520 re int dat=dfs(y,T,min(flow,edge[i].w));
521 res+=dat; flow-=dat;
522 edge[i].w-=dat;edge[edge[i].eg].w+=dat;
523 }
524 }
525 return res;
526 }
527 inline int dinic(){
528 re int res=0;
529 while(bfs()) res+=dfs(S,T,inf);
530 return res;
531 }
知识兔