競程小抄

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

int row, col;
while (cin >> row >> col) {
    vector<vector<int>> v(row+1, vector<int>(col+1));
    for (int i = 1, tmp; i <= row; i++) for (int j = 1; j <= col; j++) {
        cin >> v[i][j];
        v[i][j] += v[i-1][j] - v[i-1][j-1] + v[i][j-1];
    }
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    cout << v[ex][ey]-v[ex][sy-1]-v[sx-1][ey]+v[sx-1][sy-1] << '\n';
}

vector<int> par(N), sz(N, 1); // N 為節點總數
int Find(int x) { return par[x] == x ? x : par[x] = Find(par[x]); }
void Union(int x, int y) {
    x = Find(x); y = Find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    par[y] = x; sz[x] += sz[y]; sz[y] = 0;
}
int getSize(int x) { return sz[Find(x)]; }
// iota(all(par), 0);

struct DisjointSet {
    int n, fa[MXN], sz[MXN]; // save() is like recursive
    vector<pair<int*,int>> h; // undo() is like return
    vector<int> sp;
    void init(int tn) {
        n=tn;
        for (int i=0; i<n; i++) sz[fa[i]=i]=1;
        sp.clear(); h.clear();
    }
    void assign(int *k, int v) {
        h.PB({k, *k});
        *k=v;
    }
    void save() { sp.PB(SZ(h)); }
    void undo() {
        assert(!sp.empty());
        int last=sp.back(); sp.pop_back();
        while (SZ(h)!=last) {
            auto x=h.back(); h.pop_back();
            *x.F=x.S;
        }
    }
    int f(int x) {
        while (fa[x]!=x) x=fa[x];
        return x;
    }
    void uni(int x, int y) {
        x=f(x); y=f(y);
        if (x==y) return;
        if (sz[x]<sz[y]) swap(x, y);
        assign(&sz[x], sz[x]+sz[y]);
        assign(&fa[y], x);
    }
} djs;
int main() {
    djs.init(5);
    djs.save();
    djs.uni(0,1);
    djs.uni(2,3);
    cout << (djs.f(0)==djs.f(1)) << "\n"; // 1
    djs.undo(); 
    djs.uni(1,2);
    cout << (djs.f(1)==djs.f(2)) << "\n"; // 1
}

vector<int> v, bit;
int n;
void add(int x, int val) { for (; x <= n; x += x&-x) bit[x] += val; }
int query(int x) { 
    int sum = 0;
    for (; x > 0; x -= x&-x) sum += bit[x];
    return sum;
}
int main() {
    int a, b; cin >> n >> a >> b;
    v.resize(n);
    for (auto &i : v) cin >> i;
    bit.assign(n+1, 0);
    for (int i = 0; i< n; i++) add(i+1, v[i]);
    cout << query(b) - query(a-1);
}

int n; // n 為節點數
struct Node {
    int data, tag;
    Node() : data(0), tag(0) {}
};
vector<Node> seg;
int get_val(int l, int r, int id) {
    return seg[id].data + seg[id].tag * (r-l+1);
}
void pull(int l, int r, int id) {
    int m = (l+r)>>1;
    seg[id].data = get_val(l, m, id<<1) + get_val(m+1, r, id<<1|1);
}
void push(int l, int r, int id) {
    if (seg[id].tag) {
        seg[id].data += seg[id].tag * (r-l+1);
        seg[id<<1].tag += seg[id].tag;
        seg[id<<1|1].tag += seg[id].tag;
        seg[id].tag = 0;
    }
}
void build(vector<int> &v, int l = 0, int r = n-1, int id = 1) {
    if (l == r) return void(seg[id].data = v[l]);
    int m = (l+r)>>1;
    build(v, l, m, id<<1);
    build(v, m+1, r, id<<1|1);
    seg[id].data = seg[id<<1].data + seg[id<<1|1].data;
}
void update(int ql, int qr, int v, int l = 0, int r = n-1, int id = 1) {
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) return void(seg[id].tag += v);
    push(l, r, id); int m = (l+r)>>1;
    update(ql, qr, v, l, m, id<<1);
    update(ql, qr, v, m+1, r, id<<1|1);
    pull(l, r, id);
}
int query(int ql, int qr, int l = 0, int r = n-1, int id = 1) {
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) return get_val(l, r, id);
    push(l, r, id); int m = (l+r)>>1;
    return query(ql, qr, l, m, id<<1) + query(ql, qr, m+1, r, id<<1|1); 
}
signed main() {
    cin >> n; vector<int> v(n);
    seg.assign(n<<2|1, Node());
    for (auto &i : v) cin >> i;
    build(v);
    cout << query(0, 3) << '\n';
    update(1, 3, 5);
    cout << query(0, 3) << '\n';
}

int timer, pos[MAXN], sz[MAXN];
vector<int> g[MAXN]; // 樹的鄰接表
void dfs(int now, int pa) {
    pos[now] = ++timer;   // 紀錄節點在序列中的位置
    sz[now] = 1;          // 子樹大小初始化為1（包含自己）
    for (int v : g[now]) {
        if (v == pa) continue;
        dfs(v, now);
        sz[now] += sz[v]; // 累加子節點的大小
    }
}

struct Node {
    int l, r;
    mutable int v;
    Node(const int &il, const int &ir, const int &iv): l(il), r(ir), v(iv) {}
    bool operator<(const Node &o) const { return l < o.l; }
};
set<Node> odt; const int p = 1e9+7;
inline Node *_copy(set<Node>::iterator x) { return new Node(x->l, x->r, x->v); }
auto _split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it->l == x) return it;
    auto k = _copy(--it);
    odt.erase(it);
    odt.insert(Node(k->l, x-1, k->v));
    return odt.insert(Node(x, k->r, k->v)).fi;
}
int _query(int l, int r) {
    auto itr = _split(r+1), itl = _split(l);
    int sum = 0;
    for (; itl != itr; itl++) sum = (sum + itl->v%p * (itl->r - itl->l + 1)%p) % p;
    return sum;
}
void _assign(int l, int r, int v) {
    auto itr = _split(r+1), itl = _split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, v));
}
void _add(int l, int r, int v) {
    auto itr = _split(r+1), itl = _split(l);
    vector<Node> vec;
    for (auto it = itl; it != itr; it++) vec.emplace_back(*it), vec.back().v = (vec.back().v+v) % p;
    odt.erase(itl, itr);
    for (auto &i : vec) odt.insert(i);
}
void _dup(int l1, int r1, int l2, int r2) {
    auto itr1 = _split(r1+1), itl1 = _split(l1);
    vector<Node> vec;
    for (; itl1 != itr1; itl1++) vec.emplace_back(*itl1);
    auto itr2 = _split(r2+1), itl2 = _split(l2);
    odt.erase(itl2, itr2);
    for (auto &i : vec) odt.insert(Node(i.l-l1+l2, i.r-l1+l2, i.v));
}
void _swap(int l1, int r1, int l2, int r2) {
    if (l1 > l2) { swap(l1, l2); swap(r1, r2); }
    auto itr1 = _split(r1+1), itl1 = _split(l1);
    vector<Node> va, vb;
    for (auto it = itl1; it != itr1; it++) va.emplace_back(*it);
    auto itr2 = _split(r2+1), itl2 = _split(l2);
    for (auto it = itl2; it != itr2; it++) vb.emplace_back(*it);
    itr1 = _split(r1+1), itl1 = _split(l1); // 記得重新 split (l1, r1)，因為經過了 split (l2, r2) set 內已經變了
    odt.erase(itl1, itr1);
    itr2 = _split(r2+1), itl2 = _split(l2); // 同理
    odt.erase(itl2, itr2);
    for (auto &i : va) odt.insert(Node(i.l-l1+l2, i.r-l1+l2, i.v));
    for (auto &i : vb) odt.insert(Node(i.l-l2+l1, i.r-l2+l1, i.v));
}

void _rev(int l, int r) {
    if (l > r) swap(l, r); // !
    auto itr = _split(r+1), itl = _split(l);
    vector<Node> vec;
    for (auto it = itl; it != itr; it++) vec.emplace_back(*it);
    odt.erase(itl, itr);
    for (auto &i : vec) odt.insert(Node(r-i.r+l, r-i.l+l, i.v));
}
signed main() { WA();
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        odt.insert(Node(i, i, x));
    }
    while (m--) {
        int cmd, l1, l2, r1, r2, val;
        cin >> cmd >> l1 >> r1; l1--, r1--;
        if (cmd == 1) cout << _query(l1, r1) << '\n';
        else if (cmd == 2) {
            cin >> val;
            _assign(l1, r1, val);
        } else if (cmd == 3) {
            cin >> val;
            _add(l1, r1, val);
        } else if (cmd == 4) {
            cin >> l2 >> r2; l2--, r2--;
            _dup(l1, r1, l2, r2);
        } else if (cmd == 5) {
            cin >> l2 >> r2; l2--, r2--;
            _swap(l1, r1, l2, r2);
        } else _rev(l1, r1);
    }
    for (auto &i : odt) for (int j = i.l; j <= i.r; j++) cout << i.v%p << ' ';
}

string text, pattern;
cin >> text >> pattern;
string m = pattern + "#" + text;
int n = m.size(); vector<int> p(n);
for (int i = 1; i < n; i++) {
    int j = p[i-1];
    while (j > 0 && m[i] != m[j]) j = p[j-1];
    p[i] = j + (m[i] == m[j]);
}
int i;
for (i = pattern.size()+1; i < n; i++) if (p[i] == pattern.size()) break;
if (i == n) cout << "n\n";
else cout << "y\n";

const int N = 2e7+10;
string s, t;      // 原串, 改造串
int p[N], n;      // p[i] 表示以 t[i] 為中心的回文子串半徑, 改造串長度
void manacher() {
    int l = 0, r = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i <= r) p[i] = min(p[l + r - i], r - i + 1);
        else p[i] = 1;
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        if (i + p[i] - 1 > r) {
            l = i - p[i] + 1;
            r = i + p[i] - 1;
        }
    }
}

int main() {
    cin >> s;
    t = "@#"; // 預處理，插入特殊字符 #，首尾加哨兵
    for (char c : s) {
        t += c; t += '#';
    }
    t += '$'; n = t.size();
    manacher();
    int maxLen = 0; // 計算最大回文子串長度（原串長度）
    for (int i = 1; i < n - 1; i++) maxLen = max(maxLen, p[i] - 1);
    cout << maxLen << "\n";
}

struct Node {
    unordered_map<char, Node*> child;
    bool isWord = false;
};
void insert(Node *p, string s) {
    for (auto c : s) {
        if (!p -> child[c]) p -> child[c] = new Node;
        p = p -> child[c];
    } p -> isWord = true;
}
bool search(Node *p, string s) {
    for (auto c : s) {
        if (p -> child[c]) p = p -> child[c];
        else return false;
    } return p -> isWord;
}
Node *remove(Node *root, string s, int depth = 0) {
    if (!root) return nullptr;
    if (depth == s.size()) {
        if (root -> isWord) root -> isWord = false;
        if (root -> child.empty()) {
            delete root;
            root = nullptr;
        } return root;
    }
    char c = s[depth];
    if (root -> child[c]) {
        root -> child[c] = remove(root -> child[c], s, depth + 1);
        if (root -> child.empty() && !root -> isWord) {
            delete root;
            root = nullptr;
        } return root;
    } return root;
}
int main() { WA();
    int t; for (cin >> t; t; t--) {
        int n;
        Node *root = new Node; cin >> n;
        vector<string> v(n);
        for (auto &i : v) cin >> i;
        for (auto i : v) insert(root, i);
    }
}

const int MAXS = 500, MAXC = 26; // 狀態數最大值（所有模式串長度和）, 字母表大小 (a~z)
int out[MAXS], f[MAXS], g[MAXS][MAXC]; // 輸出函數, 失配函數, Trie的轉移函數
// 建立匹配自動機，arr是模式串數組，k是模式數
int buildMatchingMachine(string arr[], int k) {
    memset(out, 0, sizeof out); memset(g, -1, sizeof g);
    int states = 1;
    for (int i = 0; i < k; ++i) { // 建立Trie結構
        const string &word = arr[i];
        int currentState = 0;
        for (int j = 0; j < (int)word.size(); ++j) {
            int ch = word[j] - 'a';
            if (g[currentState][ch] == -1) g[currentState][ch] = states++;
            currentState = g[currentState][ch];
        } out[currentState] |= (1 << i); // 標記該狀態可匹配字串i
    }
    for (int ch = 0; ch < MAXC; ++ch) // 對Trie根節點沒有轉移的字元，設定回到根節點
        if (g[0][ch] == -1)
            g[0][ch] = 0;
    memset(f, -1, sizeof f); queue<int> q; // f[0] = 0
    for (int ch = 0; ch < MAXC; ++ch) { // 初始化深度為1的節點，失配指標為0
        if (g[0][ch] != 0) {
            f[g[0][ch]] = 0;
            q.push(g[0][ch]);
        }
    }
    while (!q.empty()) { // BFS求失配指標
        int state = q.front(); q.pop();
        for (int ch = 0; ch < MAXC; ++ch) {
            if (g[state][ch] != -1) {
                int failure = f[state];
                while (g[failure][ch] == -1)
                    failure = f[failure];
                failure = g[failure][ch];
                f[g[state][ch]] = failure;
                out[g[state][ch]] |= out[failure];
                q.push(g[state][ch]);
            }
        }
    } return states;
} // 找下一狀態 using goto和失配函數
int findNextState(int currentState, char nextInput) {
    int answer = currentState, ch = nextInput - 'a';
    while (g[answer][ch] == -1) answer = f[answer];
    return g[answer][ch];
} // 搜尋text中出現的所有模式串
void searchWords(string arr[], int k, string text) {
    buildMatchingMachine(arr, k);
    int currentState = 0;
    for (int i = 0; i < (int)text.size(); ++i) {
        currentState = findNextState(currentState, text[i]);
        if (out[currentState] == 0) continue;
        for (int j = 0; j < k; ++j) 
            if (out[currentState] & (1 << j))
                cout << "Word \"" << arr[j] << "\" appears from "
                << i - (int)arr[j].size() + 1 << " to " << i << endl;
    }
}
int main() {
    string arr[] = {"he", "she", "hers", "his"}, text = "ahishers";
    int k = sizeof(arr) / sizeof(arr[0]);
    searchWords(arr, k, text);
}

const int MAXN = 10005;  // 頂點數量上限
const int MAXM = 200005; // 邊數量上限 (無向圖需2倍)

struct Edge {
    int to;    // 邊的終點
    int next;  // 指向上一條邊的索引（同一出發點的前一條邊）
    int w;     // 邊權值（若無權可省略）
} edges[MAXM];

int head[MAXN];   // head[i]儲存從節點i出發的第一條邊的編號
int edgeCount;    // 已加邊數量計數器

void init() { // 初始化head，表示節點尚無出邊
    memset(head, -1, sizeof(head));
    edgeCount = 0;
}

void addEdge(int u, int v, int w = 0) { // 加邊 (u -> v, 權重w)
    edges[edgeCount].to = v;
    edges[edgeCount].w = w;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount++;
}

void traverse(int u) { // 遍歷節點u的所有出邊
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        int w = edges[i].w; // 對出邊執行操作，例如輸出v和w
        cout << "邊: " << u << " -> " << v << ", 權重: " << w << endl;
    }
}

int main() {
    int n, m; cin >> n >> m; // 節點數、邊數
    vector<int> v(n), dis(n, INF);
    vector<vector<PII>> g(n);
    for (auto &i : v) cin >> i;
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        g[a].pb({b, w}); g[b].pb({a, w});
    }
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    dis[0] = v[0]; pq.push({v[0], 0}); // 0 為起點
    while (!pq.empty()) {
        auto [d, node] = pq.top(); pq.pop();
        if (d > dis[node]) continue;
        for (auto &[to_idx, to_dis] : g[node])
            if (dis[node] + to_dis < dis[to_idx]) {
                dis[to_idx] = dis[node] + to_dis;
                pq.push({dis[to_idx], to_idx});
            }
    }
    for (int i = 1; i < n; i++) {
        if (dis[i] == INF) cout << "-1 ";
        else cout << dis[i] << ' ';
    }
}

vector<int> anc;
int Find(int x) { return (anc[x] == x ? x : anc[x] = Find(anc[x])); }
bool Union(int a, int b) {
    int fa = Find(a), fb = Find(b);
    if (fa > fb) swap(fa, fb);
    if (fa == fb) return false;
    return anc[fb] = fa, true;
}
anc.resize(n);
iota(all(anc), 0);
g.pb({w, a, b});
sort(all(g));
for (auto &[w, a, b] : g) if (Union(a, b)) ans += w;

int main() {
    int n, m, a, b;
    while (cin >> n >> m) {
        vector<vector<int>> v(n);
        vector<int> w(n), ans;
        while (m--) {
            cin >> a >> b;
            v[--a].pb(--b); w[b]++;
        }
        queue<int> q;
        for (int i = 0; i < n; i++) if (!w[i]) q.push(i);
        while (q.size()) {
            cout << q.front()+1 << ' ';
            for (auto i : v[q.front()]) if (!(--w[i])) q.push(i);
            q.pop();
        }
        cout << '\n';
    }
}

vector<vector<int>> v, par;
vector<int> dep;
void dfs(int x, int u) {
    par[0][x] = u;
    for (auto &i : v[x]) {
        if (i == u) continue;
        dep[i] = dep[x]+1; dfs(i, x);
    }
}
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) if (dep[par[i][a]] >= dep[b]) a = par[i][a];
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) if (par[i][a] != par[i][b])
        a = par[i][a], b = par[i][b];
    return par[0][a];
}
signed main() { WA();
    int n, q; cin >> n >> q;
    v.resize(n+1);
    for (int i = 2; i <= n; i++) {
        int k; cin >> k;
        v[i].pb(k); v[k].pb(i);
    }
    par.resize(20, vector<int>(n+1));
    dep.resize(n+1);
    dfs(1, 1); // 從根結點開始建深度表
    for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++)
        par[i][j] = par[i-1][par[i-1][j]];
    while (q--) {
        int a, b; cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
}

int n, s, e, t, a, b, w;
vector<vector<int>> g;
vector<int> vis, par;
bool BFS() {
    queue<int> q;
    vis.assign(n+1, 0); par.assign(n+1, 0);
    q.push(s); vis[s] = 1;
    while (q.size()) {
        int now = q.front(); q.pop();
        if (now == e) return true;
        for (int i = 1; i <= n; i++) if (g[now][i] && !vis[i]) {
            vis[i] = 1; par[i] = now; q.push(i);
        }
    } return false;
}
signed main() { WA();
    int c = 0;
    while (cin >> n, n) {
        g.assign(n+1, vector<int>(n+1, 0));
        cin >> s >> e >> t;
        while (t--) {
            cin >> a >> b >> w;
            g[a][b] += w; g[b][a] += w;
        }
        int ans = 0;
        while (BFS()) {
            int now = e, mnF = INF;
            while (now != s) {
                mnF = min(mnF, g[par[now]][now]);
                now = par[now];
            }
            now = e;
            while (now != s) {
                g[par[now]][now] -= mnF;
                g[now][par[now]] += mnF;
                now = par[now];
            }
            ans += mnF;
        }
        cout << ans;
    }
}

struct FlowEdge {
    int v, u;
    long long cap, flow = 0;
    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
    const long long flow_inf = 1e18;
    vector<FlowEdge> edges;
    vector<vector<int>> adj;
    int n, m = 0, s, t;
    vector<int> level, ptr;
    queue<int> q;
    Dinic(int n, int s, int t) : n(n), s(s), t(t) {
        adj.resize(n); level.resize(n); ptr.resize(n);
    }
    void add_edge(int v, int u, long long cap) {
        edges.emplace_back(v, u, cap);
        edges.emplace_back(u, v, 0);
        adj[v].push_back(m);
        adj[u].push_back(m + 1); m += 2;
    }
    bool bfs() {
        while (!q.empty()) q.pop();
        fill(level.begin(), level.end(), -1);
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int id : adj[v]) {
                if (edges[id].cap == edges[id].flow) continue;
                if (level[edges[id].u] != -1) continue;
                level[edges[id].u] = level[v] + 1;
                q.push(edges[id].u);
            }
        }
        return level[t] != -1;
    }

    long long dfs(int v, long long pushed) {
        if (pushed == 0) return 0;
        if (v == t) return pushed;
        for (int &cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
            int id = adj[v][cid];
            int u = edges[id].u;
            if (level[v] + 1 != level[u]) continue;
            long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
            if (tr == 0) continue;
            edges[id].flow += tr;
            edges[id ^ 1].flow -= tr;
            return tr;
        } return 0;
    }
    long long flow() {
        long long f = 0;
        while (true) {
            if (!bfs()) break;
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, flow_inf)) {
                f += pushed;
            }
        } return f;
    }
};

const int N = 100010;
int e[N], ne[N], h[N], w[N], idx; // 鄰接表: e儲存邊的終點, ne為下一條邊, h為頭指標, w為權值
int n, m, dist[N], cnt[N];        // dist：起點到各點距離, cnt：計數攜帶負環判斷
bool st[N];                      // st標記節點是否在隊列中
void add(int a, int b, int c) {
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
bool spfa(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    st[s] = true;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true; // 判斷負環，遍歷超過n次表示有負環
                if (!st[j]) {
                    q.push(j); st[j] = true;
                }
            }
        }
    }
    return false; // 無負環
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int start = 1; // 起點可按需設置
    if (spfa(start)) cout << "存在負權環\n";
    else {
        for (int i = 1; i <= n; i++) {
            if (dist[i] == 0x3f3f3f3f) cout << "不可達 ";
            else cout << dist[i] << " ";
        } cout << "\n";
    }
}

struct AP_Bridge {
    int n;                          
    vector<vector<int>> G;          // 圖的鄰接表
    vector<int> low, depth, AP;         
    vector<bool> visited;          
    vector<pair<int,int>> Bridge;   // 橋邊列表
    AP_Bridge(int n): n(n) {
        G.assign(n, vector<int>());
        low.assign(n, 0);
        depth.assign(n, 0);
        visited.assign(n, false);
        AP.clear(); Bridge.clear();
    }
    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void dfs(int u, int parent, int d) {
        visited[u] = true;
        depth[u] = low[u] = d;
        int child = 0; bool isAP = false;
        for (int v : G[u]) {
            if (v == parent) continue;
            if (!visited[v]) {
                dfs(v, u, d + 1);
                low[u] = min(low[u], low[v]);
                if (low[v] >= depth[u]) isAP = true;
                if (low[v] > depth[u]) Bridge.emplace_back(u, v);
                child++;
            } else low[u] = min(low[u], depth[v]);
        }
        if ((parent == -1 && child > 1) || (parent != -1 && isAP)) AP.push_back(u);
    }
    void solve() { for (int i = 0; i < n; i++) if (!visited[i]) dfs(i, -1, 1); }
};

void dfs1(int u, const vector<vector<int>>& g, vector<bool>& visited, stack<int>& st) {
    visited[u] = true;
    for (auto v : g[u]) {
        if (!visited[v]) dfs1(v, g, visited, st);
    } st.push(u);
}
void dfs2(int u, const vector<vector<int>>& rg, vector<bool>& visited) {
    visited[u] = true;
    for (auto v : rg[u]) if (!visited[v]) dfs2(v, rg, visited);
}
int kosaraju(int n, const vector<vector<int>>& g) {
    vector<bool> visited(n, false); stack<int> st;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs1(i, g, visited, st);
    }
    vector<vector<int>> rg(n);
    for (int u = 0; u < n; u++) for (auto v : g[u]) rg[v].push_back(u);
    fill(visited.begin(), visited.end(), false);
    int scc_count = 0;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (!visited[u]) {
            dfs2(u, rg, visited);
            scc_count++;
        }
    } return scc_count;
}