justiceHui

#include <bits/stdc++.h>
using namespace std;

template<typename T>
class avl_tree{
    struct avl_node{
        avl_node *l, *r, *p;
        int dep, bf, sz; T key;
        avl_node(T key) : l(nullptr), r(nullptr), p(nullptr), dep(0), bf(0), sz(1), key(key) {}
        friend int get_depth(avl_node *x){ return x ? x->dep : -1; }

justiceHui

// pair<T, vector<int>> f(T c): return opt_val, prv
// cost function must be multiplied by 2
template<class T, bool GET_MAX = false>
pair<T, vector<int>> AliensTrick(int n, int k, auto f, T lo, T hi){
    T l = lo, r = hi;
    while(l < r){
        T m = (l + r + (GET_MAX?1:0)) >> 1;
        vector<int> prv = f(m*2+(GET_MAX?-1:+1)).second;
        int cnt = 0; for(int i=n; i; i=prv[i]) cnt++;
        if(cnt <= k) (GET_MAX?l:r) = m;

justiceHui

// scaling(VE log U): https://loj.ac/s/1656688
// non-scaling(V^2E): https://loj.ac/s/1656689

template<typename flow_t, flow_t MAX_U=(1<<30), bool scale=false>
struct Dinic{
    struct edge_t{ int v, r; flow_t c, f; };
    int n;
    vector<vector<edge_t>> g;
    vector<int> lv, idx;
    Dinic(int n) : n(n) {

justiceHui

// maximum matching: https://judge.yosupo.jp/submission/117391
// mininum vertex cover, maximum anti chain: http://boj.kr/abcc944b81cf470eb67c876de3641c5c
// minimum path cover: http://boj.kr/c19b050c10ff4efab6d5cf4f68e1eb7e

struct HopcroftKarp{
    int n, m;
    vector<vector<int>> g;
    vector<int> dst, le, ri;
    vector<char> visit, track;
    HopcroftKarp(int n, int m) : n(n), m(m) { clear(); }

justiceHui

template<typename flow_t, size_t _Sz> struct PushRelabel {
    using edge_t = Edge<flow_t>;
    int n, b, dist[_Sz], count[_Sz+1];
    flow_t excess[_Sz];
    bool active[_Sz];
    vector<edge_t> g[_Sz];
    vector<int> bucket[_Sz];
    void clear(){ for(int i=0; i<_Sz; i++) g[i].clear(); }
    void addEdge(int s, int e, flow_t x){
        g[s].emplace_back(s, e, x, (int)g[e].size());

justiceHui

#include <bits/stdc++.h>
using namespace std;

// O(nm + n^2 log U)
template<typename flow_t, size_t _Sz, flow_t _Inf=1'000'000'007>
struct ExcessScalingMaximumFlow{
public:
    struct Edge{
        int v, r; flow_t c, f;
        Edge() = default;

justiceHui

// RREF Test : https://www.acmicpc.net/problem/20307 (http://boj.kr/72e7455edc2044aa93cd0fa347b44c81)
// Rank Test : https://www.acmicpc.net/problem/15737 (Tutte Matrix, http://boj.kr/bc9bbe60a5144744acf94289368c2e01)
// Det  Test : https://judge.yosupo.jp/problem/matrix_det (https://judge.yosupo.jp/submission/62842)
// Inv  Test : https://www.acmicpc.net/problem/9254 (http://boj.kr/2e9185babd8b4c049b534d80c6951893)


template<typename T> // return {rref, rank, det, inv}
tuple<vector<vector<T>>, int, T, vector<vector<T>>> Gauss(vector<vector<T>> a, bool square=true){
  int n = a.size(), m = a[0].size(), rank = 0;
  vector<vector<T>> out(n, vector<T>(m, 0)); T det = T(1);

justiceHui

#include <bits/stdc++.h>
#define zero_stl(v, sz) fill(v.begin(), v.begin()+(sz), 0)
using namespace std;

template<const int MAX_V, typename flow_t, typename cost_t, flow_t FLOW_INF, cost_t COST_INF, const int SCALE = 16>
class CostScalingMCMF {
public:
    struct Edge{
        int v; flow_t c; cost_t d; int r; // next, residual capacity, weight, reverse edge
        Edge() = default;

justiceHui

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+7;

/// Knuth's Algorithm X with Dancing Link
namespace DLX{
    struct Node{ int row, sz; shared_ptr<Node> col, up, dw, le, ri; };
    using NP = shared_ptr<Node>;
    void __Cover(NP x){
        x->ri->le = x->le;

justiceHui

struct Node{
    Node *l, *r, *p;
    bool flip; int sz;
    Node(){ l = r = p = nullptr; sz = 1; flip = false; }
    bool IsLeft() const { return p && this == p->l; }
    bool IsRoot() const { return !p || (this != p->l && this != p->r); }
    friend int GetSize(const Node *x){ return x ? x->sz : 0; }
    void Rotate(){
        if(IsLeft()) r && (r->p = p), p->l = r, r = p;
        else l && (l->p = p), p->r = l, l = p;