//拓扑排序
void Top(){
for(i=1;i<=n;++i)
if(!du[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
ans[++num]=u;
for(int i=head[u];i;i=nxt[i]){
int t=to[i];
if(!--du[t]) q.push(t);
}
}
}
//有向图tarjan
void tarjan(int cur){
dfn[cur]=low[cur]=++sign;
sta[++top]=cur,insta[cur]=1;
for(int i=first[cur];i;i=next[i]){
int t=to[i];
if(!dfn[t]) tarjan(t),low[cur]=min(low[cur],low[t]);
else if(insta[t]&&low[cur]>dfn[t]) low[cur]=dfn[t];
}
if(low[cur]==dfn[cur]){
do{insta[sta[top]]=0,id[sta[top]=++sum;}while(sta[top--]!=cur);
}
}
//无向图tarjan
void tarjan(int cur,int in_E){
dfn[cur]=low[cur]=++sign;
for(int i=first[cur];i;i=next[i]){
int t=to[i];
if(!dfn[t]){
tarjan(t,i);
low[cur]=min(low[cur],low[t]);
if(low[t]>dfn[cur]){
bridge[i]=bridge[i^1]=1;
}
}
else if(i!=(in_E^1)){
low[cur]=min(low[cur],dfn[t]);
}
}
}
void Make_id(int cur,int Id){
id[cur]=Id;
for(int i=first[cur];i;i=next[i]){
int t=to[i];
if(id[t]||bridge[i]) continue;
Make_id(t,Id);
}
}
//dijkstra
int dfs(int st,int ed){
memset(dis,127,sizeof(dis));
q.push(make_pair(0,st)); dis[st]=0;
while(!q.empty()){
int u=q.top().second; q.pop();
for(int i=first[u];i;i=next[i]){
int t=to[i];
if(dis[t]>dis[u]+w[i]){
dis[t]=dis[u]+w[i];
q.push(make_pair(-dis[t],t));
}
}
}
return dis[ed];
}
//spfa
void spfa(int st){
queue<int> q; dis[st]=0; q.push(st);
while(!q.empty()){
int x=q.front(); q.pop();
vis[x]=0;
for(int i=first[x];i;i=next[i]){
int t=to[i];
if(dis[t]>dis[x]+w[i]){
dis[t]=dis[x]+w[i];
if(!vis[t]){vis[t]=1;q.push(t);}
}
}
}
}
//dfs_spfa找负环
void dfs(int u){
if(vis[u]){flag=1;return;}
vis[u]=1;
if(flag) return;
for(int i=first[u];i;i=next[i]){
int t=to[i];
if(dis[t]>dis[u]+w[i]){
dis[t]=dis[u]+w[i];
dfs(t);
}
}vis[u]=0;
}
//Kruscal
void Kruskal(){
sort(E+1,E+m+1,cmp);
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
int x=find(E[i].u),y=find(E[i].v);
if(x!=y){
father[x]=y;
add(x,y,E[i].w),add(y,x,E[i].w);
}
}
}
