Template

default

/*
  @file: 0x3f.cpp
  @School: HTU
  @version: c++17
  @copyright: A_king
  @author: A_king
*/
#include <bits/stdc++.h>
using namespace std;
void INIT();
namespace Template {
    #define inf 0x3f3f3f3f
    #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
    #define FREOPEN freopen("in.in", "r", stdin);freopen("out.out", "w", stdout)
    #define out(x...) cout << #x <<" => ";Println(x);
    #define endl '\n'
    #define pb push_back
    #define pf push_front
    #define len(x) (int)(x).size()
    #define all(x) (x).begin(), (x).end()
    #define YES puts("YES")
    #define Yes puts("Yes")
    #define yes puts("yes")
    #define NO puts("NO")
    #define No puts("No")
    #define no puts("no")
    const double PI = acos(-1);const double eps = 1e-6;const int mod = 998244353;
    int Mod(int x) {if (x < 0) x += mod;if (x >= mod) x -= mod;return x;}
    template<class T>T ksm(T a, long long b) {T res = 1;while (b) {if (b & 1) res *= a;a *= a;b >>= 1;}return res;}
    struct Z {
        int x;
        Z(int x = 0) : x(Mod(x)) {}
        Z(long long x) : x(Mod(x % mod)) {}
        int val() const {return x;}
        Z operator-() const {return Z(Mod(mod - x));}
        Z inv() const {assert(x != 0);return ksm(*this, mod - 2);}
        Z &operator*=(const Z &T) {x = (long long)(x) * T.x % mod;return *this;}
        Z &operator+=(const Z &T) {x = Mod(x + T.x);return *this;}
        Z &operator-=(const Z &T) {x = Mod(x - T.x);return *this;}
        Z &operator/=(const Z &T) {return *this *= T.inv();}
        friend Z operator*(const Z &T, const Z &Y) {Z res = T;res *= Y;return res;}
        friend Z operator+(const Z &T, const Z &Y) {Z res = T;res += Y;return res;}
        friend Z operator-(const Z &T, const Z &Y) {Z res = T;res -= Y;return res;}
        friend Z operator/(const Z &T, const Z &Y) {Z res = T;res /= Y;return res;}
    };
    typedef vector<Z> VZ;typedef vector<VZ> VVZ;typedef long long ll;typedef pair<double, double> PDD;typedef pair<ll, ll> PLL;typedef pair<int, int> PII;typedef pair<int, PII> PIII;typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<ll> VL;typedef vector<VL> VVL;typedef vector<PII> VP;typedef vector<VP> VVP;typedef vector<string> VS;typedef vector<VS> VVS;
    template<typename T> inline T Max(T &a, T b){if (a < b) a = b;return a;}template<typename T> inline T Max(T &a, T b, T c){a = Max(a, b);a = Max(a, c);return a;}
    template<typename T> inline T Min(T &a, T b){if (a > b) a = b;return a;}template<typename T> inline T Min(T &a, T b, T c){a = Min(a, b);a = Min(a, c);return a;}
    template<typename T> inline T Abs(T a){if (a < 0) a = -1 * a;return a;}
    template<typename T>T Gcd(T a, T b){return b ? Gcd(b, a % b) : a;}
    template<typename T> inline void Swap(T &a, T &b){T temp = a;a = b;b = temp;}
    template<typename T> inline void read(T &x) {x = 0;short sgn = 1;char c = getchar();while (c < 48 || 57 < c) {if (c == 45) sgn = -1;c = getchar();}while (48 <= c && c <= 57) {x = (x << 3) + (x << 1) + c - 48;c = getchar();}x *= sgn;}
    template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);}
    template<typename ...U>void Println(U... u) {int last_index = sizeof...(U) - 1, index = 0;auto printer = [last_index, &index]<typename Args>(Args args){if (last_index == index++) cout << args << endl;else cout << args << ", ";};(printer(u), ...);}
}
using namespace Template;

// __builtin_popcount(x); 返回x中1的个数 ^^ 32 - __builtin_clz(x);32位整数的位数 ^^ __builtin_parity(x);1的奇偶，偶为0，奇为1
// accumulate(begin(), end(), start_val); 数组求和
// min_element(begin(), end()); 最小元素的迭代器
// max_element(begin(), end()); 最大元素的迭代器
// minmax_element(begin(), end()); PII类型返回两个迭代器
// nth_element(begin(), begin() + k_th, end(), less<int>()); //下标从begin()开始，默认寻找第k小的数
// priority_queue<type, vector<type>, greater<type>> q; 大根堆，重载大于号
// map<key, value> key -> PII √, unordered_map可能导致二次时间复杂度
// vector find(begin(), end(), val()) rotate(begin(), mid(), end())左循环运动
const int N = 1e6 + 10, M = 2e6 + 10;



void solve(int group_Id) {
    
}

signed main()
{
#ifdef A_king
    FREOPEN;
    clock_t CLOCK = clock();
#endif
    // int T;read(T);
    int T = 1;
    INIT();for (int i = 1;i <= T;i ++) solve(i);
#ifdef A_king
    cerr << "Run Time: " << (double)(clock() - CLOCK) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}
void INIT() {
    
    return ;
}

default2

/*
  @file: 0x3f.cpp
  @School: HTU
  @version: c++17
  @copyright: A_king
  @author: A_king
*/
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f

template<typename T> inline void read(T &x) {x = 0;short sgn = 1;char c = getchar();while (c < 48 || 57 < c) {if (c == 45) sgn = -1;c = getchar();}while (48 <= c && c <= 57) {x = (x << 3) + (x << 1) + c - 48;c = getchar();}x *= sgn;}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);}

const int N = 1e5 + 10;
typedef long long ll;


signed main()
{
#ifdef A_king
    freopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endif
    
    return 0;
}

ST表

struct ST {
    int n;
    VVI st;
    VI lg;
    ST (int n, VI arr) : n(n), lg(n + 1), st(n + 1, VI (22)) {
        function<void(void)> Init = [&]() {
            for (int i = 1;i <= n;i ++) st[i][0] = arr[i];
            for (int i = 1; i <= n; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
            for (int j = 1;j < lg[n];j ++) {
                for (int i = 1;i + (1 << j) - 1 <= n;i ++) {
                    st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
                }
            }
        };
        Init();
    }
    int query(int l, int r) {
        int k = lg[r - l + 1] - 1;
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

树状数组（Binary Indexed Tree/Fenwick Tree）

template<typename T>
struct BIT {
    int n;
    vector<T> a;
    BIT(int n) : n(n), a(n + 1) {}
    static constexpr int lowbit(int x) { return x & -x;}
    void update(int pos, T val) {
        for (int i = pos;i <= n;i += lowbit(i)) {a[i] += val;}
    }
    T query(int pos) {
        T res = 0;
        for (int i = pos;i > 0;i -= lowbit(i)) {res += a[i];}
        return res;
    }
    T query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

线段树（Segment Tree）(加）

template<typename T>
struct SegT {
    #define lo (o << 1)
    #define ro (o << 1 | 1)
    #define L(x) tr[(x)].lc
    #define R(x) tr[(x)].rc
    #define V(x) tr[(x)].val
    #define LEN(x) (R(x) - L(x) + 1)
    #define mid(x) (L(x) + R(x) >> 1)
    struct Node {
        T val;
        int lc, rc;
        int lazy;
    };
    const int n;
    vector<Node> tr;
    SegT(int n, vector<T> arr) : n(n), tr((n << 2) + 10) {
        function<void(int, int, int)> build = [&](int o, int l, int r) {
            L(o) = l, R(o) = r, tr[o].lazy = 0;
            if (l == r) {
                V(o) = arr[l];
            }else {
                build(lo, l, mid(o)), build(ro, mid(o) + 1, r);
                pushup(o);
            }
        };
        build(1, 1, n);
    }
    void pushup(int o) {// TODO: 利用左右儿子信息维护当前节点的信息
        V(o) = V(lo) + V(ro);
    }
    void pushdown(int o) {// TODO: 将懒标记下传
        if (tr[o].lazy && L(o) != R(o)) {
            V(lo) = V(lo) + tr[o].lazy * LEN(lo);
            V(ro) = V(ro) + tr[o].lazy * LEN(ro);
            tr[lo].lazy += tr[o].lazy;
            tr[ro].lazy += tr[o].lazy;
            tr[o].lazy = 0;
        }
    }
    void update(int l, int r, T d, int o = 1) {
        if (L(o) >= l && R(o) <= r) {// TODO: 修改区间
            V(o) += LEN(o) * d;
            tr[o].lazy += d;
        }else {
            pushdown(o);
            if (l <= mid(o)) update(l, r, d, lo);
            if (r > mid(o)) update(l, r, d, ro);
            pushup(o);
        }
    }
    T query(int l, int r, int o = 1)
    {
        if (L(o) >= l && R(o) <= r) {// TODO 需要补充返回值
            return V(o);  
        }else {
            pushdown(o);
            T res = 0;
            if (l <= mid(o)) res += query(l, r, lo);
            if (r > mid(o)) res += query(l, r, ro);
            return res;
        }
    }
};

线段树（Segment Tree）(加&乘）

template<typename T>
struct SegT {
    #define lo (o << 1)
    #define ro (o << 1 | 1)
    #define L(x) tr[(x)].lc
    #define R(x) tr[(x)].rc
    #define V(x) tr[(x)].val
    #define LEN(x) (R(x) - L(x) + 1)
    #define mid(x) (L(x) + R(x) >> 1)
    int mod;
    struct Node {
        T val;
        int lc, rc;
        T lazy1, lazy2;
    };
    const int n;
    vector<Node> tr;
    SegT(int n, vector<T> arr, int mod) : n(n), tr((n << 2) + 10), mod(mod) {
        function<void(int, int, int)> build = [&](int o, int l, int r) {
            L(o) = l, R(o) = r, tr[o].lazy2 = 0, tr[o].lazy1 = 1;
            if (l == r) {
                V(o) = arr[l];
            }else {
                build(lo, l, mid(o)), build(ro, mid(o) + 1, r);
                pushup(o);
            }
        };
        build(1, 1, n);
    }
    void pushup(int o) {// TODO: 利用左右儿子信息维护当前节点的信息
        V(o) = (V(lo) + V(ro)) % mod;
    }
    void pushdown(int o) {// TODO: 将懒标记下传
        V(lo) = (V(lo) * tr[o].lazy1 + tr[o].lazy2 * LEN(lo)) % mod;
        V(ro) = (V(ro) * tr[o].lazy1 + tr[o].lazy2 * LEN(ro)) % mod;
        tr[lo].lazy1 = tr[lo].lazy1 * tr[o].lazy1 % mod;
        tr[ro].lazy1 = tr[ro].lazy1 * tr[o].lazy1 % mod;
        tr[lo].lazy2 = (tr[lo].lazy2 * tr[o].lazy1 + tr[o].lazy2) % mod; 
        tr[ro].lazy2 = (tr[ro].lazy2 * tr[o].lazy1 + tr[o].lazy2) % mod; 
        tr[o].lazy2 = 0;
        tr[o].lazy1 = 1;
    }
    void update1(int l, int r, T d, int o = 1) {
        if (L(o) >= l && R(o) <= r) {// TODO: 修改区间
            V(o) = V(o) * d % mod;
            tr[o].lazy1 = tr[o].lazy1 * d % mod;
            tr[o].lazy2 = tr[o].lazy2 * d % mod;
        }else {
            pushdown(o);
            if (l <= mid(o)) update1(l, r, d, lo);
            if (r > mid(o)) update1(l, r, d, ro);
            pushup(o);
        }
    }
    void update2(int l, int r, T d, int o = 1) {
        if (L(o) >= l && R(o) <= r) {// TODO: 修改区间
            V(o) = (V(o) + LEN(o) * d) % mod;
            tr[o].lazy2 = (tr[o].lazy2 + d) % mod;
        }else {
            pushdown(o);
            if (l <= mid(o)) update2(l, r, d, lo);
            if (r > mid(o)) update2(l, r, d, ro);
            pushup(o);
        }
    }
    T query(int l, int r, int o = 1)
    {
        if (L(o) >= l && R(o) <= r) {// TODO 需要补充返回值
            return V(o);  
        }else {
            pushdown(o);
            T res = 0;
            if (l <= mid(o)) res = (res + query(l, r, lo)) % mod;
            if (r > mid(o)) res = (res + query(l, r, ro)) % mod;
            return res;
        }
    }
};

线性基

template<typename T>
struct Linear_base {
    T ba[61], temp[61];
    bool flag = false;
    Linear_base() {
        function<void(void)> Init = [&]() {
            for (int i = 0;i < 60;i ++) {
                ba[i] = temp[i] = 0;
            }
        };
        Init();
    }
    void insert(T x) {
        for (int i = 60;i >= 0; i--)
            if (x & (1ll << i))
                if (!ba[i]) {
                    ba[i] = x;
                    return;
                }
            else x ^= ba[i];
        flag = true;
    }
    bool check(T x) {
        for (int i = 60; i >= 0; i--)
            if (x & (1ll << i))
                if (!ba[i]) return false;
                else x ^= ba[i];
        return true;
    }
    T qmax(T res = 0) {
        for (int i = 60;i >= 0; i--)
            res = max(res, res ^ ba[i]);
        return res;
    }
    T qmin() {
        if (flag) return 0;
        for (int i = 0; i <= 60; i++)
            if (ba[i]) return ba[i];
        return -1;
    }
    T query(T k) {// 数组中可以得到的异或k大
        T res = 0;
        int cnt = 0;
        k -= flag;
        if (!k) return 0;
        for (int i = 0; i <= 60; i++)
        {
            for (int j = i - 1; ~j; j--)
                if (ba[i] & (1ll << j)) ba[i] ^= ba[j];
            if (ba[i]) temp[cnt++] = ba[i];
        }
        if (k >= (1ll << cnt)) return -1;
        for (int i = 0; i < cnt; i++)
            if (k & (1ll << i)) res ^= temp[i];
        return res;
    }
};

AC自动机（出现次数）

struct AC {
    int tr[M][26], fail[M], e[M], tot;//字典树 指针 标号
    int cnt[N], val[M];// cnt表示第i个字符串出现的次数
    AC() {
        function<void(void)> Init = [&]() {
            tot = 0;
            for (int i = 0;i < N;i ++) {
                cnt[i] = 0;
            }
            for (int i = 0;i < M;i ++) {
                val[i] = fail[i] = e[i] = 0;
                for (int j = 0;j < 26;j ++) {
                    tr[i][j] = 0;
                }
            }
        };
        Init();
    }
    void insert(char *s, int id){// 字典树插入
        int u = 0;
        for(int i = 1;s[i];i ++){
            if(!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++ tot;
            u = tr[u][s[i] - 'a'];
        }
        e[u] = id;
    }
    queue<int> q;
    void build(){// 计算fail指针
        for(int i = 0;i < 26;i ++)
            if(tr[0][i]) q.push(tr[0][i]);
        while(q.size()){
            int u = q.front();
            q.pop();
            for(int i = 0; i < 26;i ++){
                if(tr[u][i]){
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                }else tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    int query(char *t){// 询问每个单词出现次数、返回最大次数
        int u = 0, res = 0;
        for(int i = 1;t[i];i ++){
            u = tr[u][t[i] - 'a'];
            for(int j = u;j;j = fail[j]) val[j] ++;
        }
        for(int i = 1;i <= tot;i ++){
            if(e[i]){
                res = max(res, val[i]);
                cnt[e[i]] = val[i];// 通过标号得到次数
            }
        }
        return res;
    }
};

AC自动机（出现个数）

struct AC {
    int tr[N][26], fail[N], e[N], tot;
    AC() {
        function<void(void)> Init = [&]() {
            tot = 0;
            for (int i = 0;i < N;i ++) {
                fail[i] = e[i] = 0;
                for (int j = 0;j < 26;j ++) {
                    tr[i][j] = 0;
                }
            }
        };
        Init();
    }
    void insert(char *s){// 字典树插入
        int u = 0;
        for(int i = 1;s[i];i++){
            if(!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a'];
        }
        e[u]++;
    }
    queue<int> q;
    void build(){// 计算fail指针
        for(int i = 0;i < 26;i++){
            if(tr[0][i]) q.push(tr[0][i]);
        }
        while(q.size()){
            int u = q.front();
            q.pop();
            for(int i = 0;i < 26;i++){
                if(tr[u][i]){
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    int query(char *t){// 询问几个单词出现过、当且仅当编号不同
        int u = 0, res = 0;
        for(int i = 1;t[i];i++){
            u = tr[u][t[i] - 'a'];
            for(int j = u;j && ~e[j];j = fail[j]){
                res += e[j];
                e[j] = -1;
            }
        }
        return res;
    }
};

并查集（DSU）

struct DSU {
    int n;
    vector<int> fa;
    vector<int> sz;
    DSU(int n) : n(n), fa(n + 1), sz(n + 1) {
        for (int i = 1;i <= n;i ++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    void merge(int a, int b) {
        a = find(a), b = find(b);
        if (sz[a] > sz[b]) swap(a, b);
        fa[a] = b;
        sz[b] += sz[a];
    }
    bool test(int a, int b) {return find(a) == find(b);}
};

最近公共祖先（distance）

struct LCA {
    int root;
    int fa[N][20], dist[N][20], dep[N];
    LCA(int root) : root(root) {
        function<void(void)> Init = [&]() {
            for (int i = 0;i < N;i ++) {
                dep[i] = 0;
                for (int j = 0;j < 20;j ++) {
                    fa[i][j] = dist[i][j] = 0;
                }
            }
        };
        function<void(int, int)> dfs = [&](int u, int father) {
            fa[u][0] = father;
            dep[u] = dep[fa[u][0]] + 1;
            for (int i = 1;i < 20;i ++) {
                fa[u][i] = fa[fa[u][i - 1]][i - 1];
                dist[u][i] = dist[u][i - 1] + dist[fa[u][i - 1]][i - 1];
            }
            for (int i = h[u];~i;i = ne[i]) {
                int j = e[i];
                if (j == father) continue;
                dist[j][0] = w[i];
                dfs(j, u);
            }
        };
        Init();
        dfs(root, root);
    }
    int lca (int x, int y) {
        int res = 0;
        if(dep[x] > dep[y]) swap(x, y);
        int tmp = dep[y] - dep[x];
        for (int j = 0;tmp;j ++, tmp >>= 1) {
            if(tmp & 1) res += dist[y][j], y = fa[y][j];
        }
        if (x == y) return res;
        for (int i = 19;i >= 0;i --) {
            if (fa[x][i] != fa[y][i]) {
                res += dist[x][i] + dist[y][i];
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        res += dist[x][0] + dist[y][0];
        return res;
    }
};

最近公共祖先（点）

struct LCA {
    //fa[u][i]表示u的第2^i个祖先,dep[u]表示u的深度
    int root;
    int fa[N][20], dep[N];
    LCA(int root) : root(root) {
        function<void(void)> Init = [&]() {
            for (int i = 0;i < N;i ++) {
                dep[i] = 0;
                for (int j = 0;j < 20;j ++) {
                    fa[i][j] = 0;
                }
            }
        };
        function<void(int, int)> dfs = [&](int u, int father) {
            fa[u][0] = father;//当前点的第2^0个祖先就是我的父亲
            dep[u] = dep[fa[u][0]] + 1;//当前点的深度就是父亲的深度 + 1
            for (int i = 1;i < 20;i ++) {
                fa[u][i] = fa[fa[u][i - 1]][i - 1];//u的第2^i个祖先,就是第2^(i - 1)个祖先的第2^(i - 1)个祖先
            }
            for (int i = h[u];~i;i = ne[i]) {//遍历子节点
                int j = e[i];
                if (j == father) continue;
                dfs(j, u);
            }
        };
        Init();
        dfs(root, root);
    }
    int lca (int x, int y) {
        if(dep[x] > dep[y]) swap(x, y);//令y为深度大的点
        int tmp = dep[y] - dep[x];//得到深度差
        for (int j = 0;tmp;j ++, tmp >>= 1) {//二进制递减深度
            if(tmp & 1) y = fa[y][j];
        }
        if (x == y) return x;
        //如果不在一个小子树上,继续往上找
        for (int i = 19;i >= 0;i --) {//这里从上往下，使得x和y到距离最近公共祖先最近的点
            if (fa[x][i] != fa[y][i]) {
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
};

Manacher（长度）

struct Man {
    int n;
    string str, nstr;
    int lens[2 * N];
    Man(int n) : n(n) {
        function<void(void)> Init = [&]() {
            str = nstr = "";
            for (itn i = 0;i < 2 * n + 5;i ++) {
                len[i] = 0;
            }
        };
        Init();
    }
    void init()//返回字符串长度、str为字符串、nstr为新字符串
    {
        int j = 2;
        nstr += '@', nstr += '#';
        for (int i = 0; i < str.length(); i++)
        {
            nstr += str[i];
            nstr += '#';
        }
        nstr += '*';
    }
    int man()//返回最长字符串、len为字符串长度
    {
        int mx = 0, id = 1, max_len = 0;
        for (int i = 1; i < nstr.length(); i++)
        {
            lens[i] = i < mx ? min(mx - i, lens[2 * id - i]) : 1;
            while (nstr[i + lens[i]] == nstr[i - lens[i]]) lens[i]++;
            if (lens[i] + i > mx)
            {
                mx = lens[i] + i;
                id = i;
            }
            max_len = max(max_len, lens[i]);
        }
        return max_len - 1;
    }
};

Manacher（子串）

struct Man {
    int n;
    string str, nstr;
    int lens[2 * N];
    Man(int n) : n(n) {
        function<void(void)> Init = [&]() {
            str = nstr = "";
            for (itn i = 0;i < 2 * n + 5;i ++) {
                len[i] = 0;
            }
        };
        Init();
    }
    void init()//str为字符串、nstr为新字符串
    {
        int j = 2;
        nstr += '@', nstr += '#';
        for (int i = 0; i < str.length(); i++)
        {
            nstr += str[i];
            nstr += '#';
        }
        nstr += '*';
    }
    string man() {//返回最长字符子串、len为字符串长度
        int mx = 0, id = 1, max_len = 0, startx = 2, lenx = 1;
        for (int i = 1; i < nstr.length(); i++)
        {
            lens[i] = i < mx ? min(mx - i, lens[2 * id - i]) : 1;
            while (nstr[i + lens[i]] == nstr[i - lens[i]]) lens[i]++;
            if(lens[i] > max_len){
                    startx = i;
                    lenx = lens[i];
                }
            if (lens[i] + i > mx)
            {
                mx = lens[i] + i;
                id = i;
            }
            max_len = max(max_len, lens[i]);
        }
        nstr = nstr.substr(startx, lenx);
        if((max_len - 1) & 1){
            string str = nstr.substr(1);
            reverse(str.begin(), str.end());
            nstr = str + nstr;
        }else{
            reverse(nstr.begin(), nstr.end());
            string str = nstr;
            reverse(nstr.begin(), nstr.end());
            nstr = str + nstr;
        }
        string cc = "";
        for(int i = 0;i < nstr.length();i++){
            if(nstr[i] != '#') cc += nstr[i];
        }
        return cc;
    }
};

Tarjan（强连通分量）

struct Tarjan {
    int n;
    int dfn[N], low[N], sta[N], gro[N], tot[N];
    bool instack[N];//是否在栈内
    int stop, bcnt, dindex;//stop栈内元素个数,bcnt为分组的组号,dindex为时间戳
    Tarjan(int n) : n(n) {
        function<void(void)> Init = [&]() {
            stop = bcnt = dindex = 0;
            for (int i = 0;i <= n;i ++) {
                dfn[i] = low[i] = sta[i] = gro[i] = tot[i] = 0;
                instack[i] = false;
            }
        };
        Init();
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++ dindex;//初始都为时间戳
        instack[u] = true;//加入栈内
        sta[++ stop] = u;
        // out(stop);
        for (int i = h[u];~i;i = ne[i]) {
            int j = e[i];
            if (!dfn[j]){
                tarjan(j);
                if (low[j] < low[u]) low[u] = low[j];
            }else if (instack[j] && dfn[j] < low[u]) low[u] = dfn[j];
        }
        if (dfn[u] == low[u]) {
            bcnt ++;
            int j;
            do {
                j = sta[stop--];
                instack[j] = false;
                gro[j] = bcnt;
                tot[bcnt] ++;
            }while (j != u);
        }
    }
};

Tarjan（割边）

struct Tarjan {
    int n;
    int dfn[N], low[N], father[N];//dfn(u)为节点u搜索的次序编号(时间戳),low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
    int dfs_clock, cnt_bridge;//dfs_clock时间戳、cnt_bridge割边数量
    bool isbridge[N];//是否是割边
    vector<PII> res;// 割边集合
    Tarjan(int n) : n(n) {
        function<void(void)> Init = [&]() {
            res.clear();
            dfs_clock = cnt_bridge = 0;
            for (int i = 0;i <= n;i ++) {
                dfn[i] = low[i] = father[i] = 0;
                isbridge[i] = false;
            }
        };
        Init();
    }
    void tarjan(int u, int fa) {
        father[u] = fa;//父亲节点
        low[u] = dfn[u] = ++ dfs_clock;
        for (int i = h[u];~i;i = ne[i]) {
            int v = e[i];
            if (!dfn[v]) {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) {
                    isbridge[v] = true;// 如果isbridge为真表示father[v] -> v为一条割边
                    res.push_back({father[v], v});
                    ++ cnt_bridge;
                }
            } else if (dfn[v] < dfn[u] && v != fa) {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
};

Tarjan（割点）

struct Tarjan {
    //dfn(u)为节点u搜索的次序编号(时间戳),low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
    int n;
    int dfn[N], low[N], cut[N];
    int stop, bcnt, dindex;//dindex为时间戳
    Tarjan(int n) : n(n) {
        function<void(void)> Init = [&]() {
            stop = bcnt = dindex = 0;
            for (int i = 0;i <= n;i ++) {
                dfn[i] = low[i] = cut[i] = 0;
            }
        };
        Init();
    }
    void tarjan(int u, int fa) {
        dfn[u] = low[u] = ++ dindex;//初始都为时间戳
        int child = 0;

        for (int i = h[u];~i;i = ne[i]) {
            int j = e[i];
            if (!dfn[j]){
                tarjan(j, fa);
                low[u] = min(low[u], low[j]);
                if (low[j] >= dfn[u] && u != fa)
                    cut[u] = 1;
                if(u == fa)
                    child ++;
            }else if (j != u) low[u] = min (low[u], dfn[j]);
        }
        if (child >= 2 && u == fa)
            cut[u] = 1;
    }
};

割点求删除一个点得到最多连通块

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ dindex;//初始都为时间戳
    int child = 0;
    for (int i = h[u];~i;i = ne[i]) {
        int j = e[i];
        if (!dfn[j]){
            tarjan(j, fa);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) {
                // low比dfn序大，证明j无法回到u，故可以删去u使得j所在连通块被分离出去
                child ++;
            }
        }else low[u] = min (low[u], dfn[j]);
    }
    if (u != fa) child ++;// 如果不是根节点，显然可以使得上方连通块也被分离
    res = Max(res, child);
}
// 最终图中删去一个点可以得到的最多连通块为：图中原有的连通块数量 + res - 1;