//无向图的双连通分量
int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; // 割顶的bccno无意义
struct Edge { int u, v; };
vector G[maxn], bcc[maxn];
stack S;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
Edge e = (Edge){u, v};
if(!pre[v]) { // 没有访问过v
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv); // 用后代的low函数更新自己
if(lowv >= pre[u]) {
iscut[u] = true;
bcc_cnt++; bcc[bcc_cnt].clear();
for(;;) {
Edge x = S.top(); S.pop();
if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }
if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }
if(x.u == u && x.v == v) break;
}
}
}
else if(pre[v] < pre[u] && v != fa) {
S.push(e);
lowu = min(lowu, pre[v]); // 用反向边更新自己
}
}
if(fa < 0 && child == 1) iscut[u] = 0;
return lowu;
}
void find_bcc(int n) {
// 调用结束后S保证为空，所以不用清空
memset(pre, 0, sizeof(pre));
memset(iscut, 0, sizeof(iscut));
memset(bccno, 0, sizeof(bccno));
dfs_clock = bcc_cnt = 0;
for(int i = 0; i < n; i++)
if(!pre[i]) dfs(i, -1);
};
//无向图求桥 & 双连通分量
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int nc = G[u].size();
REP(i, nc)
{
int v = edges[G[u][i]].to;
if(!pre[v])
{
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; //标记所有桥
}
else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);
}
return low[u] = lowu;
}
void dfs1(int u)
{
bccno[u] = bcc_cnt;
int nc = G[u].size();
REP(i, nc)
{
int v = edges[G[u][i]].to;
if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);//不经过桥
}
}
void find_bcc()
{
CLR(pre, 0); CLR(bccno, 0);
dfs_clock = bcc_cnt = 0;
REP(i, n) if(!pre[i]) dfs(i, -1);
REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i);
}
//有向图的强连通分量
vector G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack S;
void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(!pre[v]) {
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
} else if(!sccno[v]) {
lowlink[u] = min(lowlink[u], pre[v]);
}
}
if(lowlink[u] == pre[u]) {
scc_cnt++;
for(;;) {
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
}
void find_scc(int n)
{
dfs_clock = scc_cnt = 0;
memset(sccno, 0, sizeof(sccno));
memset(pre, 0, sizeof(pre));
for(int i = 0; i < n; i++)
if(!pre[i]) dfs(i);
};
//无向图的欧拉回路 保存在G中
void add(int u, int v)
{
g[u][v] = g[v][u] = 1;
degree[u]++, degree[v]++;
}
void Euler()
{
FF(i, 1, n+1) if(degree[i])
{
int u = i;
while(true)
{
FF(j, 1, n+1) if(g[u][j] && g[j][u])
{
g[j][u] = 0;
degree[u]--, degree[i]--;
u = j;
break;
}
if(u == i) break;
}
}
}
//2-sat dfs版本
struct TwoSAT {
int n;
vector G[maxn*2];
bool mark[maxn*2];
int S[maxn*2], c;
bool dfs(int x) {
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x] = true;
S[c++] = x;
for (int i = 0; i < G[x].size(); i++)
if (!dfs(G[x][i])) return false;
return true;
}
void init(int n) {
this->n = n;
for (int i = 0; i < n*2; i++) G[i].clear();
memset(mark, 0, sizeof(mark));
}
// x = xval or y = yval
void add_clause(int x, int xval, int y, int yval) {
x = x * 2 + xval;
y = y * 2 + yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool solve() {
for(int i = 0; i < n*2; i += 2)
if(!mark[i] && !mark[i+1]) {
c = 0;
if(!dfs(i)) {
while(c > 0) mark[S[--c]] = false;
if(!dfs(i+1)) return false;
}
}
return true;
}
};
//堆优化的Dijkstra
struct Edge {
int from, to, dist;
};
struct HeapNode {
int d, u;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
};
struct Dijkstra {
int n, m;
vector edges;
vector G[maxn];
bool done[maxn]; // 是否已永久标号
int d[maxn]; // s到各个点的距离
int p[maxn]; // 最短路中的上一条弧
void init(int n) {
this->n = n;
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int dist) {
edges.push_back((Edge){from, to, dist});
m = edges.size();
G[from].push_back(m-1);
}
void dijkstra(int s) {
priority_queue Q;
for(int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
memset(done, 0, sizeof(done));
Q.push((HeapNode){0, s});
while(!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to], e.to});
}
}
}
}
// dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）
void GetShortestPaths(int s, int* dist, vector
* paths) {
dijkstra(s);
for(int i = 0; i < n; i++) {
dist[i] = d[i];
paths[i].clear();
int t = i;
paths[i].push_back(t);
while(t != s) {
paths[i].push_back(edges[p[t]].from);
t = edges[p[t]].from;
}
reverse(paths[i].begin(), paths[i].end());
}
}
};
//spfa判负环
struct Edge {
int from, to;
double dist;
};
struct spfa {
int n, m;
vector edges;
vector G[maxn];
bool inq[maxn]; // 是否在队列中
double d[maxn]; // s到各个点的距离
int p[maxn]; // 最短路中的上一条弧
int cnt[maxn]; // 进队次数
void init(int n) {
this->n = n;
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, double dist) {
edges.push_back((Edge){from, to, dist});
m = edges.size();
G[from].push_back(m-1);
}
bool negativeCycle() {
queue Q;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); }
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
}
}
}
return false;
}
};
//kruskal求次小生成树 maxcost[i][j]为i->j的瓶颈路
//对于MST边u, v maxcost[u][v] = 0
int n, m, x[maxn], y[maxn], p[maxn];
int pa[maxn];
int findset(int x) { return pa[x] != x pa[x] = findset(pa[x]) : x; }
//G保存MST C保存MST边权
vector G[maxn];
vector C[maxn];
struct Edge {
int x, y;
double d;
bool operator < (const Edge& rhs) const {
return d < rhs.d;
}
};
Edge e[maxn*maxn];
double maxcost[maxn][maxn];
vector nodes;
void dfs(int u, int fa, double facost) {
for(int i = 0; i < nodes.size(); i++) {
int x = nodes[i];
maxcost[u][x] = maxcost[x][u] = max(maxcost[x][fa], facost);
}
nodes.push_back(u);
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v != fa) dfs(v, u, C[u][i]);
}
}
double MST() {
sort(e, e+m);
for(int i = 0; i < n; i++) { pa[i] = i; G[i].clear(); C[i].clear(); }
int cnt = 0;
double ans = 0;
for(int i = 0; i < m; i++) {
int x = e[i].x, y = e[i].y, u = findset(x), v = findset(y);
double d = e[i].d;
if(u != v) {
pa[u] = v;
G[x].push_back(y); C[x].push_back(d);
G[y].push_back(x); C[y].push_back(d);
ans += d;
if(++cnt == n-1) break;
}
}
return ans;
}
//prim求次小生成树
//use[u][v] = 2时，边在MST上
//use[u][v] = 1时，原图存在边。
//f[u][v]表示u->v的最小瓶颈路 初始化为0
double prim()
{
int pre[maxn] = {-1};
bool vis[maxn] = {0};
double d[maxn], ret = 0;
FF(i, 1, n+1) d[i] = INF; d[1] = 0;
FF(i, 1, n+1)
{
int pos;
double tmp = INF;
FF(j, 1, n+1) if(!vis[j] && d[j] < tmp) tmp = d[j], pos = j;
if(pre[pos] != -1)
{
use[pre[pos]][pos] = use[pos][pre[pos]] = 2;
FF(j, 1, n+1) if(vis[j]) f[pos][j] = f[j][pos] = max(f[j][pre[pos]], g[pre[pos]][pos]);
}
vis[pos] = 1;
ret += d[pos];
FF(j, 1, n+1) if(!vis[j] && use[pos][j] && g[pos][j] < d[j]) d[j] = g[pos][j], pre[j] = pos;
}
return ret;
}
//LCA
struct LCA {
int n;
int fa[maxn]; // 父亲数组
int cost[maxn]; // 和父亲的费用
int L[maxn]; // 层次（根节点层次为0）
int anc[maxn][logmaxn]; // anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i]
int maxcost[maxn][logmaxn]; // maxcost[p][i]是i和anc[p][i]的路径上的最大费用
// 预处理，根据fa和cost数组求出anc和maxcost数组
void preprocess() {
for(int i = 0; i < n; i++) {
anc[i][0] = fa[i]; maxcost[i][0] = cost[i];
for(int j = 1; (1 << j) < n; j++) anc[i][j] = -1;
}
for(int j = 1; (1 << j) < n; j++)
for(int i = 0; i < n; i++)
if(anc[i][j-1] != -1) {
int a = anc[i][j-1];
anc[i][j] = anc[a][j-1];
maxcost[i][j] = max(maxcost[i][j-1], maxcost[a][j-1]);
}
}
// 求p到q的路径上的最大权
int query(int p, int q) {
int tmp, log, i;
if(L[p] < L[q]) swap(p, q);
for(log = 1; (1 << log) <= L[p]; log++); log--;
int ans = -INF;
for(int i = log; i >= 0; i--)
if (L[p] - (1 << i) >= L[q]) { ans = max(ans, maxcost[p][i]); p = anc[p][i];}
if (p == q) return ans; // LCA为p
for(int i = log; i >= 0; i--)
if(anc[p][i] != -1 && anc[p][i] != anc[q][i]) {
ans = max(ans, maxcost[p][i]); p = anc[p][i];
ans = max(ans, maxcost[q][i]); q = anc[q][i];
}
ans = max(ans, cost[p]);
ans = max(ans, cost[q]);
return ans; // LCA为fa[p]（它也等于fa[q]）
}
};
//固定根的最小树型图，邻接矩阵写法
struct MDST {
int n;
int w[maxn][maxn]; // 边权
int vis[maxn]; // 访问标记，仅用来判断无解
int ans; // 计算答案
int removed[maxn]; // 每个点是否被删除
int cid[maxn]; // 所在圈编号
int pre[maxn]; // 最小入边的起点