CCF-CSP 算法板子

// 加法溢出判定 (a, b >= 0)
bool addOverflow(ll a, ll b) { return a > LLONG_MAX - b; }
// 乘法安全写法: 先转 long double 估商, 或直接用 __int128
ll mul(ll a, ll b, ll m) { return (ll)((__int128)a * b % m); }

// 负数取模: C++ 中 (-7) % 3 == -1, 不是 2
int mod(int x, int m) { x %= m; return x < 0 ? x + m : x; }
// 浮点比较
int sgn(double x) { return x < -EPS ? -1 : (x > EPS ? 1 : 0); }
bool eq(double a, double b) { return fabs(a - b) < EPS; }

#include <bits/stdc++.h>          // GCC 万能头; 非 GCC 需逐个 include
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) (x).begin(), (x).end()
#define sz(x)  (int)(x).size()
#define pb     push_back
#define fi     first
#define se     second
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;              // 10^9 级, 两倍不溢出 int
const ll  LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;              // 1e9+7
const double EPS = 1e-8;
const int dx4[] = {0, 0, 1, -1}, dy4[] = {1, -1, 0, 0};   // 四方向; 八方向补对角
ll qpow(ll a, ll b, ll m = MOD) {        // 快速幂 O(log n)
    ll r = 1 % m; a %= m; if (a < 0) a += m;
    for (; b; b >>= 1, a = a * a % m) if (b & 1) r = r * a % m;
    return r;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }   // O(log n)
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }        // 先除后乘防溢出

// 快读: 比 cin/scanf 快 3~5 倍, 适合 10^6 级输入. 依赖 <cstdio>
namespace io {
const int BUF = 1 << 20;
char buf[BUF]; int len = 0, pos = 0;
inline char gc() {
    if (pos == len) { len = (int)fread(buf, 1, BUF, stdin); pos = 0; if (len <= 0) return 0; } return buf[pos++]; }
inline bool readInt(int &x) {            // 支持负号; 读到 EOF 返回 false
    char c = gc();
    while (c && (c < '0' || c > '9') && c != '-') c = gc();
    if (!c) return false;
    bool neg = false; if (c == '-') { neg = true; c = gc(); }
    for (x = 0; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    if (neg) x = -x;
    return true;
}
// readLL 与 readInt 完全同构, 仅把 int 换成 ll (长整数必须走这个)
inline void writeLL(ll x) {              // 快写: 比 printf 快约 2 倍
    if (x < 0) { putchar('-'); x = -x; }
    char stk[24]; int top = 0;
    do { stk[top++] = char('0' + x % 10); x /= 10; } while (x);     while (top) putchar(stk[--top]); }
}  // namespace io

// __int128: 约 ±1.7e38. GCC/Clang 支持, MSVC 不支持; 无 IO 重载必须手写
__int128 readI128() {
    __int128 x = 0; int sign = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
    for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c - '0');
    return x * sign;
}
void writeI128(__int128 x) {
    if (x == 0) { putchar('0'); return; }
    if (x < 0) { putchar('-'); x = -x; }
    char stk[45]; int top = 0;
    while (x > 0) { stk[top++] = char('0' + (int)(x % 10)); x /= 10; }     while (top) putchar(stk[--top]); }
string i128str(__int128 v) {             // std::to_string 不支持 __int128
    if (v == 0) return "0";
    bool ng = v < 0; if (ng) v = -v;
    string s; while (v > 0) { s += char('0' + (int)(v % 10)); v /= 10; }
    if (ng) s += '-';
    reverse(s.begin(), s.end()); return s;
}
// 乘法防溢出: __int128 c = (__int128)a * b % MOD;  再转回 ll

bool check(int x);   // 要求: 在候选区间上单调 (false...false true...true)
// 【写法一】闭区间 [lo,hi], 最小可行值; mid 下取整
int lowerBound(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;      // 防 (lo+hi) 溢出
        if (check(mid)) hi = mid; else lo = mid + 1;
    } return lo; }
// 【写法二】闭区间 [lo,hi], 最大可行值; mid 上取整
int upperBound(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;  // 上取整, 否则死循环
        if (check(mid)) lo = mid; else hi = mid - 1;
    } return lo; }
// 【写法三】左闭右开, 维护 check(l)=false 且 check(r)=true, 返回 r (最小可行值)
int solveOpen(int lo, int hi) {
    int l = lo - 1, r = hi + 1;            // 两端必须各外扩一格!
    while (l + 1 < r) { int mid = l + (r - l) / 2;
        if (check(mid)) r = mid; else l = mid; } return r; }

// lower_bound: 首个 >= x; upper_bound: 首个 > x. 均 O(log n), 要求已排序
int p1 = (int)(lower_bound(a, a + n, x) - a);           // [a, a+n)
int p3 = (int)(lower_bound(a, a + n, x, greater<int>()) - a);   // 下降序列
// vector 同理; x 出现次数 = upper_bound - lower_bound
double f(double x);                                     // 单调函数
double solveDouble(double lo, double hi) {              // 浮点二分
    for (int it = 0; it < 100; ++it) {                  // 100 轮精度约 1e-30
        double mid = (lo + hi) / 2;
        if (f(mid) >= 0) hi = mid; else lo = mid;
    } return lo; }

// 二分答案 = 二分枚举答案 + 贪心/模拟判定. 前提: 答案单调 + check 可 O(n) 实现
bool check(ll x);
ll solveMaxMin(ll lo, ll hi) {           // 最大值最小: check 随 x 增大 false -> true
    while (lo < hi) { ll mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid; else lo = mid + 1; } return lo; }
ll solveMinMax(ll lo, ll hi) {           // 最小值最大: check 随 x 增大 true -> false
    while (lo < hi) { ll mid = lo + (hi - lo + 1) / 2;
        if (check(mid)) lo = mid; else hi = mid - 1; } return lo; }

// 完整可编译示例: 洛谷 P1873 砍树 (求最大的 H 使 sum(a[i]-H | a[i]>H) >= M)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
int n, a[N]; ll m;
bool check(ll k) {                       // 锯片高 k 时能否拿到 >= m 木材
    ll sum = 0;
    for (int i = 1; i <= n; ++i) if (a[i] > k && (sum += a[i] - k) >= m) return true;
    return sum >= m;
}
int main() {
    scanf("%d%lld", &n, &m);
    ll lo = 0, hi = 0;                   // 答案区间 [0, max a]
    for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); hi = max(hi, (ll)a[i]); }
    while (lo < hi) { ll mid = lo + (hi - lo + 1) / 2;   // 最大可行值 -> 上取整
        if (check(mid)) lo = mid; else hi = mid - 1; }
    printf("%lld\n", lo); return 0;
}

ll s[N], d[N];                          // 全局数组默认清零; d 需开到 n+2
void build1D() { for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i]; }   // O(n) 预处理
ll rangeSum(int l, int r) { return s[r] - s[l - 1]; }                     // O(1) 查询
void addRange(int l, int r, ll v) { d[l] += v; d[r + 1] -= v; }           // O(1) 区间加
void rebuild1D() { for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + d[i]; } // O(n) 还原

ll s[N][N], d[N][N];                    // d 需开到 n+2 行、m+2 列
void build2D() {                        // O(nm) 预处理, O(1) 矩形查询
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
ll rectSum(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}
void addRect(int x1, int y1, int x2, int y2, ll v) {   // O(1) 矩形加: 四角打标记
    d[x1][y1] += v;      d[x2 + 1][y1] -= v;
    d[x1][y2 + 1] -= v;  d[x2 + 1][y2 + 1] += v;       // 容斥: 多减的加回来
}
void seed2D() {                         // 用原数组 a 初始化差分数组 d
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
        d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
}
void rebuild2D() {                      // 还原: 一遍二维前缀和
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
        d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
}

void add(int i); void del(int i); bool ok();
int shortestWindow() {                  // 最短的满足条件的连续区间. O(n)
    int l = 1, ans = INF;
    for (int r = 1; r <= n; ++r) {
        add(r);
        while (l <= r && ok()) { ans = min(ans, r - l + 1); del(l++); }  // 可行则收缩
    } return ans; }
// 求最长满足条件的区间: while 条件改成 !ok(), 更新 ans = max(ans, r - l + 1)
// 判定型双指针 (两有序数组求两数之和, O(n+m)): i 从 0 递增, j 从 m-1 递减,
// 若 a[i]+b[j] < target 则 ++i, 否则 --j
int q[N];                               // 单调队列求滑动窗口最值: 窗口长 k, O(n)
void windowMax() {                      // 存下标而非值! 求最小值改比较符为 >=
    int head = 1, tail = 0;
    for (int i = 1; i <= n; ++i) {
        while (head <= tail && a[q[tail]] <= a[i]) --tail;  // 队尾更小 -> 永无出头之日
        q[++tail] = i;
        if (q[head] <= i - k) ++head;                       // 队头滑出 (先判越界)
        if (i >= k) printf("%d ", a[q[head]]);              // 队头即窗口最大值
    }
}

vector<int> xs;
void compress() {                       // O(n log n)
    xs.assign(a + 1, a + n + 1);                       // 1. 拷贝
    sort(xs.begin(), xs.end());                        // 2. 排序
    xs.erase(unique(xs.begin(), xs.end()), xs.end());  // 3. 去重
    for (int i = 1; i <= n; ++i)                       // 4. 映射为 1-based 排名
        a[i] = (int)(lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin()) + 1;
}
// 反查第 r 名的原值: xs[r - 1];  原值 x 的排名: lower_bound(...) - begin() + 1
// 值域大小: int len = (int)xs.size();

struct Seg { int l, r; } seg[N];
bool cmpR(const Seg &x, const Seg &y) { return x.r < y.r; }
int maxDisjoint() {   // 【区间调度】最多两两不交的区间 (相接算不重叠). O(n log n)
    sort(seg + 1, seg + n + 1, cmpR);           // 按右端点升序
    int cnt = 0, last = -INF;
    for (int i = 1; i <= n; ++i) if (seg[i].l >= last) { ++cnt; last = seg[i].r; } return cnt; }
int minPoints() {     // 【区间选点】最少点命中所有区间. O(n log n)
    sort(seg + 1, seg + n + 1, cmpR);           // 在右端点放点最划算
    int pts = 0, lastP = -INF;
    for (int i = 1; i <= n; ++i) if (seg[i].l > lastP) { ++pts; lastP = seg[i].r; } return pts; }

ll huffman() {                          // 每次合并最小的两个. O(n log n)
    priority_queue<ll, vector<ll>, greater<ll>> pq;   // 第三个参数才是小根堆
    for (int i = 1; i <= n; ++i) pq.push(a[i]);
    ll cost = 0;
    while (pq.size() > 1) {
        ll x = pq.top(); pq.pop(); ll y = pq.top(); pq.pop();
        cost += x + y; pq.push(x + y);                // 合并代价
    } return cost; }
struct Job { ll d, p; } job[N];
bool cmpD(const Job &x, const Job &y) { return x.d < y.d; }
ll workScheduling() {   // 反悔贪心 (USACO Work Scheduling). O(n log n)
    sort(job + 1, job + n + 1, cmpD);                 // 按截止时间升序
    priority_queue<ll, vector<ll>, greater<ll>> pq;   // 小根堆: 已选中最差的
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        pq.push(job[i].p); ans += job[i].p;           // 先接受
        if ((ll)pq.size() > job[i].d) { ans -= pq.top(); pq.pop(); }   // 超期反悔
    } return ans; }
// 邻项交换法 (排序贪心): 设交换相邻两项不影响其他项, 比较两种顺序推出 cmp
// 例 (NOIP 2012 国王游戏 / 耍杂技的牛): 按 a*b 升序
struct Cow { ll a, b; } cow[N];
bool cmpCow(const Cow &x, const Cow &y) { return x.a * x.b < y.a * y.b; }

void sortDemo() {
    sort(a + 1, a + n + 1);                              // 升序 O(n log n)
    sort(a + 1, a + n + 1, greater<int>());              // 降序
    int len = (int)(unique(a + 1, a + n + 1) - (a + 1)); // 去重(先 sort), 有效元素 a[1..len]
    nth_element(a + 1, a + k, a + n + 1);                // O(n): 第 k 小就位, 左 <= 它 <= 右
    // 第 k 大 = nth_element(a+1, a+n-k+1, a+n+1) 后的 a[n-k+1]
}
struct Node { int x, y, z; };                            // 多关键字: tie 字典序比较
bool operator<(const Node &A, const Node &B) { return tie(A.x, A.y, A.z) < tie(B.x, B.y, B.z); }
// 混合升降序: return tie(A.x, B.y) < tie(B.x, A.y);   // x 升序, y 降序

bool isLeap(int y) { return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }
const int MD[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int daysInMonth(int y, int m) { return (m == 2 && isLeap(y)) ? 29 : MD[m]; }
ll daysFromCivil(ll y, int m, int d) {   // 日期 -> 绝对天数, 1970-01-01 = 0, 相减即天数差
    y -= (m <= 2);
    ll era = (y >= 0 ? y : y - 399) / 400;
    ll yoe = y - era * 400;
    ll doy = (153 * (m + (m > 2 ? -3 : 9)) + 2) / 5 + d - 1;
    ll doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
    return era * 146097 + doe - 719468;
}
int weekday(ll y, int m, int d) { return (int)((daysFromCivil(y, m, d) % 7 + 10) % 7); } // 0=周一

string toBase(ll x, int B) {             // 十进制 -> B 进制 (2<=B<=36). O(log_B x)
    if (x == 0) return "0";
    bool neg = x < 0; if (neg) x = -x;
    string s;
    while (x > 0) { int d = (int)(x % B); s += char(d < 10 ? '0' + d : 'A' + d - 10); x /= B; }
    if (neg) s += '-';
    reverse(s.begin(), s.end()); return s;
}
ll fromBase(const string &s, int B) {    // B 进制 -> 十进制. O(len)
    ll x = 0;
    for (char c : s) { if (c == '-') continue;
        x = x * B + ((c <= '9') ? c - '0' : (c >= 'a' ? c - 'a' + 10 : c - 'A' + 10)); } return x; }
int modString(const string &s, int m) {  // 大数取模: 逐位取模. O(len)
    ll r = 0;
    for (char c : s) r = (r * 10 + (c - '0')) % m;
    return (int)r;
}

// 高精度整数 (十进制, 低位在前). 加/减 O(n), 乘 O(n*m), 除 O(n*m*log10)
struct Big {
    vector<int> d; bool neg = false;                // d[0] 是个位
    Big(long long x = 0) {
        if (x < 0) { neg = true; x = -x; }
        if (x == 0) d.push_back(0);
        while (x) { d.push_back((int)(x % 10)); x /= 10; }
    }
    void trim() {                                   // 去前导零并修正 -0
        while (d.size() > 1 && d.back() == 0) d.pop_back();
        if (d.size() == 1 && d[0] == 0) neg = false;
    }
};
int cmpAbs(const Big &a, const Big &b) {            // 无符号比较: -1 / 0 / 1
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1;
    for (int i = (int)a.d.size() - 1; i >= 0; --i)
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    return 0;
}
Big add(const Big &a, const Big &b) {               // 无符号加法
    Big c; c.d.assign(max(a.d.size(), b.d.size()) + 1, 0);
    for (size_t i = 0; i < a.d.size(); ++i) c.d[i] += a.d[i];
    for (size_t i = 0; i < b.d.size(); ++i) c.d[i] += b.d[i];
    for (size_t i = 0; i + 1 < c.d.size(); ++i) { c.d[i+1] += c.d[i]/10; c.d[i] %= 10; }     c.trim(); return c; }
Big sub(const Big &a, const Big &b) {               // 无符号减法 (要求 a >= b)
    Big c = a;
    for (size_t i = 0; i < b.d.size(); ++i) c.d[i] -= b.d[i];
    for (size_t i = 0; i + 1 < c.d.size(); ++i) if (c.d[i] < 0) { c.d[i] += 10; c.d[i+1]--; }     c.trim(); return c; }
Big mul(const Big &a, const Big &b) {               // 无符号乘法 (先累加后统一进位)
    Big c; c.d.assign(a.d.size() + b.d.size(), 0);
    for (size_t i = 0; i < a.d.size(); ++i) for (size_t j = 0; j < b.d.size(); ++j)
        c.d[i+j] += a.d[i] * b.d[j];
    for (size_t i = 0; i + 1 < c.d.size(); ++i) { c.d[i+1] += c.d[i]/10; c.d[i] %= 10; }     c.trim(); return c; }
// 高精度 * 单精度: 直接 mul(a, Big(k)) 即可 (下面 divBig 就这么用)
Big divSmall(const Big &a, int b, int &rem) {       // 高精度 / 单精度, rem 回传余数
    Big c; c.d.assign(a.d.size(), 0); rem = 0;
    for (int i = (int)a.d.size() - 1; i >= 0; --i) {
        int cur = rem * 10 + a.d[i]; c.d[i] = cur / b; rem = cur % b;
    }     c.trim(); return c; }
Big divBig(const Big &a, const Big &b, Big &r) {    // 竖式长除法 + 二分试商
    Big q; q.d.assign(a.d.size(), 0); r = Big(0);
    for (int i = (int)a.d.size() - 1; i >= 0; --i) {
        r.d.insert(r.d.begin(), a.d[i]); r.trim();  // r = r * 10 + a.d[i]
        int lo = 0, hi = 9, t = 0;                  // 试商 0..9
        while (lo <= hi) { int mid = (lo + hi) / 2;
            if (cmpAbs(mul(b, Big(mid)), r) <= 0) { t = mid; lo = mid + 1; } else hi = mid - 1; }
        q.d[i] = t; r = sub(r, mul(b, Big(t)));
    }
    q.trim(); return q;
}
void printBig(const Big &a) {                       // 输出
    if (a.neg) putchar('-');
    for (int i = (int)a.d.size() - 1; i >= 0; --i) putchar(char('0' + a.d[i]));
}

vector<string> split(const string &s, char delim) {   // 按分隔符分割 (保留空段)
    vector<string> res; string cur;
    for (char c : s) { if (c == delim) { res.push_back(cur); cur.clear(); } else cur += c; }
    res.push_back(cur); return res;
}
vector<string> splitWs(const string &s) {             // 按空白分割 (跳过连续空白)
    vector<string> res; string tok; stringstream ss(s);
    while (ss >> tok) res.push_back(tok);
    return res;
}
string trim(const string &s) {                        // 去首尾空白
    size_t l = s.find_first_not_of(" \t\r\n");
    if (l == string::npos) return "";
    size_t r = s.find_last_not_of(" \t\r\n");
    return s.substr(l, r - l + 1);
}
// 读整行 (cin >> 后残留换行, 用 >> ws 吃掉): string line; getline(cin >> ws, line);

void stlDemo() {
    priority_queue<int> pqMax;                            // 大根堆 (默认)
    priority_queue<int, vector<int>, greater<int>> pqMin; // 小根堆
    sort(a, a + n);                                       // 必须先升序
    do { /* 使用 a[0..n-1] */ } while (next_permutation(a, a + n));  // false=已最大
    bitset<1005> bs; bs.set(); bs.reset(); bs.flip(); bs[3] = 1;
    int c = (int)bs.count();                              // 数 1 的个数
    bs |= (bs << 2);                                      // 位运算即集合运算
}
// 优先队列自定义比较: 与 sort 的 cmp 相反! 返回 true 表示 a 优先级"低于" b
// struct Cmp { bool operator()(const pii &x, const pii &y) const { return x.first > y.first; } };
// priority_queue<pii, vector<pii>, Cmp> pq;

// unordered_map 防卡哈希: splitmix64 雪崩函数 + 随机种子
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// unordered_map<ll, int, custom_hash> mp;

// 标准 main 骨架, 直接抄 (依赖 1.1 的万能头与 using namespace std)
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;                    // 多测
    while (T--) solve();
    return 0;
}

// 0/1 背包搜索: 可行性 + 最优性(剩余价值上界) + 顺序剪枝, 最坏 O(2^n)
int n,C,w[N],v[N],suf[N],best;                 // suf[i]=v[i..n] 之和
bool cmp(int a,int b){return 1LL*v[a]*w[b]>1LL*v[b]*w[a];}   // 单位价值降序
void dfs(int i,int cw,int cv){
  if(cw>C)return;                                          // 可行性剪枝
  if(cv+suf[i]<=best)return;                               // 最优性剪枝(上界)
  if(i>n){best=max(best,cv);return;}
  if(cw+w[i]<=C)dfs(i+1,cw+w[i],cv+v[i]);                  // 顺序剪枝: 先搜"选"
  dfs(i+1,cw,cv);
}

// IDA*: 适用"求最少步数 + 状态空间大 + 判重难", 时间 O(b^limit), 空间 O(limit)
int limit;
int h(int u);                                  // 题目给出, 必须 h(u) <= 真实剩余步数
bool iddfs(int u,int d){
  if(h(u)==0)return true;                                  // 到达目标
  if(d+h(u)>limit)return false;                            // IDA* 剪枝
  for(int v:nxt(u)){if(vis[v])continue;vis[v]=1;if(iddfs(v,d+1))return true;vis[v]=0;}
  return false;
}
int solve(int s){for(limit=0;limit<=MAXD;++limit)if(iddfs(s,0))return limit;return -1;}

// 双向 BFS: 以"翻转某一位"的玩具状态空间为例; 时间约 O(b^(d/2)), 空间同
unordered_map<int,int> d1,d2;                  // 两侧到该状态的距离
vector<int> nxt(int u);                        // 题目给出的状态转移
int bfs2(int s,int t,int k){
  if(s==t)return 0;
  queue<int> q1,q2; q1.push(s); q2.push(t); d1[s]=0; d2[t]=0;
  while(!q1.empty()&&!q2.empty()){
    if(q1.size()>q2.size()){swap(q1,q2);swap(d1,d2);}      // 扩展小的一侧
    for(int sz=q1.size();sz--;){                           // 按层扩展
      int u=q1.front(); q1.pop();
      for(int v:nxt(u)){if(d1.count(v))continue;
        if(d2.count(v))return d1[u]+1+d2[v];               // 相遇
        d1[v]=d1[u]+1; q1.push(v);}
    }
  }
  return -1;
}

// 4.1 网格 BFS 最短路(边权全 1): O(n*m)
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};   // 四方向
// 八方向: dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1}
int n,m,dis[N][N];
int bfs(int sx,int sy,int tx,int ty){
  memset(dis,-1,sizeof dis); queue<pair<int,int>> q; q.push({sx,sy}); dis[sx][sy]=0;
  while(!q.empty()){
    auto [x,y]=q.front(); q.pop();
    if(x==tx&&y==ty)return dis[x][y];
    for(int d=0;d<4;++d){int nx=x+dx[d],ny=y+dy[d];
      if(nx<1||nx>n||ny<1||ny>m||dis[nx][ny]!=-1||g[nx][ny]=='#')continue;
      dis[nx][ny]=dis[x][y]+1; q.push({nx,ny});}
  }
  return -1;
}
// 4.2 多源 BFS: 所有源点 dis=0 一起入队, 求每点到最近源点距离; O(n*m)
void bfs_multi(vector<pair<int,int>>&src){
  memset(dis,-1,sizeof dis); queue<pair<int,int>> q;
  for(auto&p:src){dis[p.first][p.second]=0;q.push(p);}
  while(!q.empty()){/* 同上扩展 */}
}
// 4.3 0-1 BFS: 边权只有 0/1, deque 代替优先队列; 每点最多入队 2 次, O(n+m)
int dis[N];
void bfs01(int s){
  memset(dis,0x3f,sizeof dis); deque<int> q; dis[s]=0; q.push_front(s);
  while(!q.empty()){int u=q.front();q.pop_front();
    for(auto [v,w]:e[u])                                          // w 必须是 0 或 1
      if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;(w==0?q.push_front(v):q.push_back(v));}}
}
// 4.4 状态压缩 BFS: 状态压进 int/uint64, 数组或哈希判重; O(状态数 * 转移数)
int dis[1<<K];                                 // K <= 20 左右
int bfs_mask(int s,int t){
  memset(dis,-1,sizeof dis); queue<int> q; q.push(s); dis[s]=0;
  while(!q.empty()){int u=q.front();q.pop(); if(u==t)return dis[u];
    for(int i=0;i<K;++i){int v=u^(1<<i);if(dis[v]==-1){dis[v]=dis[u]+1;q.push(v);}}}  // 翻转第 i 位
  return -1;}                                   // 更小的 K 用数组快, 大的 K 换哈希表

// 滑雪(网格最长下降路径): 时间 O(n*m), 空间 O(n*m)
int n,m,h[N][N],f[N][N];
int dfs(int x,int y){
  if(f[x][y]!=-1)return f[x][y];                           // 命中缓存
  f[x][y]=1;
  for(int d=0;d<4;++d){int nx=x+dx[d],ny=y+dy[d];
    if(nx<1||nx>n||ny<1||ny>m||h[nx][ny]>=h[x][y])continue;
    f[x][y]=max(f[x][y],dfs(nx,ny)+1);}
  return f[x][y];}

// A* 网格最短路: h=曼哈顿距离(四方向, 可采纳且一致); 最坏 O(n*m*log), 通常远快
struct Node{int f,x,y; bool operator<(const Node&o)const{return f>o.f;}};
int astar(int sx,int sy,int tx,int ty){
  memset(dis,0x3f,sizeof dis); priority_queue<Node> q;
  dis[sx][sy]=0; q.push({abs(sx-tx)+abs(sy-ty),sx,sy});
  while(!q.empty()){
    Node c=q.top(); q.pop();
    if(c.x==tx&&c.y==ty)return dis[tx][ty];
    if(c.f>dis[c.x][c.y]+abs(c.x-tx)+abs(c.y-ty))continue;  // 过期节点
    for(int d=0;d<4;++d){int nx=c.x+dx[d],ny=c.y+dy[d];
      if(nx<1||nx>n||ny<1||ny>m||g[nx][ny]=='#')continue;
      if(dis[c.x][c.y]+1<dis[nx][ny]){dis[nx][ny]=dis[c.x][c.y]+1;
        q.push({dis[nx][ny]+abs(nx-tx)+abs(ny-ty),nx,ny});}}}
  
  return -1;
}

// DLX 精确覆盖模板: 节点数 = 1 的个数 + 列数
const int MAXN=500010;
int n,m,tot,ansn,L[MAXN],R[MAXN],U[MAXN],D[MAXN],row[MAXN],col[MAXN],siz[MAXN],head[MAXN],ans[MAXN];
void init(int r,int c){n=r; m=c;               // r 行 c 列
  for(int i=0;i<=c;++i){L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;siz[i]=0;}
  L[0]=c; R[c]=0; tot=c+1; for(int i=1;i<=r;++i)head[i]=-1;}
void add(int r,int c){                         // 第 r 行插入一个 1(列 c)
  int x=tot++; row[x]=r; col[x]=c; ++siz[c];
  D[x]=D[c]; U[x]=c; U[D[c]]=x; D[c]=x;
  if(head[r]==-1)head[r]=L[x]=R[x]=x;
  else{R[x]=R[head[r]];L[x]=head[r];L[R[head[r]]]=x;R[head[r]]=x;}
}
void remove(int c){R[L[c]]=R[c];L[R[c]]=L[c];
  for(int i=D[c];i!=c;i=D[i])for(int j=R[i];j!=i;j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];--siz[col[j]];}}
void resume(int c){for(int i=U[c];i!=c;i=U[i])for(int j=L[i];j!=i;j=L[j]){U[D[j]]=j;D[U[j]]=j;++siz[col[j]];}
  R[L[c]]=c; L[R[c]]=c;}
bool dance(int d){
  if(R[0]==0){ansn=d;return true;}                         // 所有列已覆盖
  int c=R[0]; for(int i=R[0];i!=0;i=R[i])if(siz[i]<siz[c])c=i;   // 选 1 最少的列
  remove(c);
  for(int i=D[c];i!=c;i=D[i]){
    ans[d]=row[i];
    for(int j=R[i];j!=i;j=R[j])remove(col[j]);
    if(dance(d+1))return true;
    for(int j=L[i];j!=i;j=L[j])resume(col[j]);
  }
  resume(c); return false;
}

// BFS 版求连通块个数/大小: O(n*m)
int cnt;
void flood(int sx,int sy){
  queue<pair<int,int>> q; q.push({sx,sy}); vis[sx][sy]=1;
  while(!q.empty()){
    auto [x,y]=q.front(); q.pop();
    for(int d=0;d<4;++d){int nx=x+dx[d],ny=y+dy[d];
      if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])continue;
      if(g[nx][ny]!=g[sx][sy])continue;                    // 同色/同类型才扩展
      vis[nx][ny]=1; q.push({nx,ny});}}}

// 主函数: for i,j if(!vis[i][j]) flood(i,j), ++cnt;

// 9.1 链式前向星: 最省内存最快, 支持边编号(i^1 取反向边)
int hd[N],to[M],wt[M],nxt[M],cnt=1;            // cnt 从 1 开始, 反向边 = i^1
void add(int u,int v,int w){to[++cnt]=v;wt[cnt]=w;nxt[cnt]=hd[u];hd[u]=cnt;}
void add2(int u,int v,int w){add(u,v,w);add(v,u,w);}
// 遍历出边: for(int i=hd[u];i;i=nxt[i]){int v=to[i],w=wt[i];}
// 9.2 vector 邻接表: 写法最短, 遍历方便, 不支持边编号; 默认首选
vector<pair<int,int>> e[N];                    // 加边: e[u].push_back({v,w});
// 遍历: for(auto [v,w]:e[u]){ }
// 9.3 邻接矩阵: O(1) 查边, 适合 n <= 2000 的稠密图 / Floyd / 传递闭包
int g[N][N];                                   // 加边: g[u][v]=min(g[u][v],w);

// 10.1 Kahn: O(n+m)。最终出队点数 < n 则有环
int deg[N],ord[N],tot;
bool topo(int n){
  queue<int> q; for(int i=1;i<=n;++i)if(!deg[i])q.push(i);
  while(!q.empty()){int u=q.front();q.pop();ord[++tot]=u;for(int v:e[u])if(--deg[v]==0)q.push(v);}
  return tot==n;                               // false 表示有环; 要字典序最小就换 priority_queue
}
// 10.2 DFS 三色判环: 0 未访问, 1 在栈中, 2 已完成
int col[N]; bool cyc;
void dfs(int u){
  col[u]=1;
  for(int v:e[u]){if(col[v]==1)cyc=true;else if(col[v]==0)dfs(v);}   // 指向栈中节点 => 有环
  col[u]=2;
}
// 10.3 DAG 上 DP: 按拓扑序转移(最长路/计数/方案数); O(n+m)
void dagdp(int n){for(int i=1;i<=n;++i){int u=ord[i];for(auto [v,w]:e[u])f[v]=max(f[v],f[u]+w);}}

// 11.1 Dijkstra 堆优化: 不能有负权边, O(m log n)
const int INF=0x3f3f3f3f;
int dis[N];
void dijkstra(int s){
  memset(dis,0x3f,sizeof dis);
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
  dis[s]=0; q.push({0,s});
  while(!q.empty()){
    auto [d,u]=q.top(); q.pop();
    if(d>dis[u])continue;                                  // 过期节点
    for(auto [v,w]:e[u])if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push({dis[v],v});}}
}
// 11.2 SPFA + SLF/LLL + 判负环: 最坏 O(nm), 可被构造数据卡死
int dis[N],cnt[N]; bool inq[N];
bool spfa(int s){                              // 返回 false <=> s 可达负环
  memset(dis,0x3f,sizeof dis); memset(cnt,0,sizeof cnt); memset(inq,0,sizeof inq);  // 多测必须清空
  deque<int> q; dis[s]=0; q.push_back(s); inq[s]=1;
  long long sum=0;                                         // 队内 dis 之和, 供 LLL 用
  while(!q.empty()){
    int u=q.front(); q.pop_front(); inq[u]=0; sum-=dis[u];
    for(auto [v,w]:e[u]){
      if(dis[u]+w<dis[v]){
        dis[v]=dis[u]+w; cnt[v]=cnt[u]+1;
        if(cnt[v]>=n)return false;                         // 最短路经过 >= n 条边 => 负环
        if(!inq[v]){
          inq[v]=1; sum+=dis[v];
          if(!q.empty()&&1LL*dis[v]*q.size()<sum)q.push_front(v);      // LLL
          else if(!q.empty()&&dis[v]<dis[q.front()])q.push_front(v);   // SLF
          else q.push_back(v);
        }
      }
    }
  }
  return true;
}

// 11.3 Floyd: 任意两点最短路, O(n^3), n <= 500 量级
for(int k=1;k<=n;++k)                          // k 必须在最外层!
  for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
    if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j];
// 传递闭包: bitset<N> b[N]; for(k)for(i)if(b[i][k])b[i]|=b[k];  // O(n^3/64)
// 判负环: 存在 i 使 dis[i][i] < 0
// 11.4 Johnson 全源最短路(简述): 有负权边但无负环, O(n*m*log m), 稀疏图优于 Floyd
// 超级源点 0 -> 所有点(权 0), SPFA 求势能 h[]; 有负环则无解
// 重赋权 w'(u,v)=w(u,v)+h[u]-h[v] >= 0, 对每个源点跑 Dijkstra; 还原 dis(u,v)=d'(u,v)-h[u]+h[v]

// 12.1 Kruskal + 并查集: O(m log m), 稀疏图首选
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct Edge{int u,v,w;} eg[M];
int kruskal(int n,int m){
  for(int i=1;i<=n;++i)fa[i]=i;
  sort(eg+1,eg+m+1,[](const Edge&a,const Edge&b){return a.w<b.w;});
  int sum=0,used=0;
  for(int i=1;i<=m;++i){
    int x=find(eg[i].u),y=find(eg[i].v);
    if(x==y)continue;
    fa[x]=y; sum+=eg[i].w; if(++used==n-1)break;
  }
  return used==n-1?sum:-1;                     // -1 表示不连通
}
// 12.2 Prim 朴素: O(n^2), 稠密图/完全图优于 Kruskal; g[][] 为邻接矩阵
int dis[N]; bool vis[N];
int prim(int n){
  memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[1]=0; int sum=0;   // 多测要清 vis
  for(int i=1;i<=n;++i){
    int u=0;
    for(int v=1;v<=n;++v)if(!vis[v]&&(!u||dis[v]<dis[u]))u=v;
    if(dis[u]==INF)return -1;                              // 不连通
    vis[u]=1; sum+=dis[u];
    for(int v=1;v<=n;++v)if(!vis[v]&&g[u][v]<dis[v])dis[v]=g[u][v];}
  return sum;
}
// 12.3 非严格次小生成树(简述): 先求 MST, 枚举每条非树边 (u,v,w),
//      用倍增求 MST 上 u-v 路径的最大边权 mx, ans=min(ans, sum-mx+w); O(m log m)
// 严格次小生成树: 再维护"严格次大边权", 当 w == mx 时用严格次大值替换

// 13.1 强连通分量 SCC + 缩点: O(n+m)。scc 编号是反拓扑序(编号小 => 靠近汇点)
vector<int> e[N];
int dfn[N],low[N],stk[N],top,tim,scc[N],scnt,sz[N];
void tarjan(int u){
  dfn[u]=low[u]=++tim; stk[++top]=u;
  for(int v:e[u]){
    if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
    else if(!scc[v])low[u]=min(low[u],dfn[v]);             // v 还在栈中
  }
  if(low[u]==dfn[u]){++scnt;int v;do{v=stk[top--];scc[v]=scnt;++sz[scnt];}while(v!=u);}
}
// 调用: for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
// 缩点: for(u)for(v:e[u])if(scc[u]!=scc[v])add(scc[u],scc[v]);  // 先排序去重

// 13.2 割点 & 桥(无向图, 支持重边): 链式前向星 cnt 从 1 开始, O(n+m)
int hd[N],to[M],nxt[M],cnt=1;
int dfn[N],low[N],tim,root;
bool cut[N],isbridge[M];
void add(int u,int v){to[++cnt]=v;nxt[cnt]=hd[u];hd[u]=cnt;}
void tarjan(int u,int inedge){
  dfn[u]=low[u]=++tim; int child=0;
  for(int i=hd[u];i;i=nxt[i]){int v=to[i];
    if(i==(inedge^1))continue;                             // 只跳过"来时那条边", 重边不受影响
    if(!dfn[v]){
      ++child; tarjan(v,i); low[u]=min(low[u],low[v]);
      if(low[v]>dfn[u])isbridge[i]=isbridge[i^1]=true;      // 桥
      if(low[v]>=dfn[u]&&u!=root)cut[u]=true;               // 割点(非根)
    }else low[u]=min(low[u],dfn[v]);
  }
  if(u==root&&child>1)cut[u]=true;                         // 根: 至少两个孩子才是割点
}
// 13.3 边双 eDCC(简述): 删掉所有桥后的连通块; 求完桥对非桥边 DFS 染色即可, O(n+m)
// 13.4 点双 vDCC(简述): 栈存"点", low[v]>=dfn[u] 时弹栈直到 v, 再把 u 也压入该分量;
//      每个割点属于多个点双, 点双缩点后得到"圆方树"(约 2n 个点)

// 2-SAT: O(n+m)。点 i = 真, i+n = 假
void add_clause(int a,bool av,int b,bool bv){  // (x_a == av) 或 (x_b == bv)
  int na=av?a+n:a, nb=bv?b+n:b;                // na = ¬(a==av), nb = ¬(b==bv)
  e[na].push_back(bv?b:b+n);                   // ¬(a==av) -> (b==bv)
  e[nb].push_back(av?a:a+n);                   // ¬(b==bv) -> (a==av)
}
bool solve(){
  for(int i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);
  for(int i=1;i<=n;++i)if(scc[i]==scc[i+n])return false;   // 无解
  for(int i=1;i<=n;++i)val[i]=scc[i]<scc[i+n];             // Tarjan 编号是反拓扑序
  return true;}

// 15.1 倍增法: 预处理 O(n log n), 单次查询 O(log n)
const int LG=20;                               // 2^20 > 1e6; n 到 1e5 用 17
int dep[N],fa[N][LG];
void dfs(int u,int p){
  dep[u]=dep[p]+1; fa[u][0]=p;
  for(int j=1;j<LG;++j)fa[u][j]=fa[fa[u][j-1]][j-1];
  for(int v:e[u])if(v!=p)dfs(v,u);}
int lca(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  int d=dep[u]-dep[v];
  for(int j=0;d;++j,d>>=1)if(d&1)u=fa[u][j];               // 先拉到同深度
  if(u==v)return u;
  for(int j=LG-1;j>=0;--j)if(fa[u][j]!=fa[v][j])u=fa[u][j],v=fa[v][j];
  return fa[u][0];
}
// 树上两点距离: dep[u]+dep[v]-2*dep[lca(u,v)]
// 15.2 Tarjan 离线 LCA: O(n + m*alpha(n)), 适合大量询问
int fa[N],ans[Q]; bool vis[N];
vector<pair<int,int>> qry[N];                  // qry[u] = {(v, 询问编号)}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void tarjan(int u,int p){
  vis[u]=1; fa[u]=u;
  for(int v:e[u])if(v!=p){tarjan(v,u);fa[v]=u;}            // 回溯时把子树并到 u
  for(auto [v,id]:qry[u])if(vis[v])ans[id]=find(v);        // v 已访问 => LCA = find(v)
}

// 16.1 树的直径: 两次 DFS/BFS, O(n); 不能有负权边
int far; long long best;
void dfs(int u,int p,long long d){
  if(d>best)best=d,far=u;
  for(auto [v,w]:e[u])if(v!=p)dfs(v,u,d+w);
}
// 调用: best=-1,dfs(1,0,0); best=-1,dfs(far,0,0); 此时 best 即直径长度
// 16.2 树的直径(树形 DP): O(n), 可处理负权边
long long dp[N],D;
void dfs2(int u,int p){
  dp[u]=0;
  for(auto [v,w]:e[u])if(v!=p){dfs2(v,u);
    D=max(D,dp[u]+dp[v]+w);                                // 先用旧 dp[u] 再更新, 避免同子树走两次
    dp[u]=max(dp[u],dp[v]+w);}
}
// 16.3 树的重心: O(n)。删去后最大连通块 <= n/2; 重心至多两个且相邻
int sz[N],mx[N],ct;                           // 依赖全局 n
void dfs3(int u,int p){
  sz[u]=1; mx[u]=0;
  for(int v:e[u])if(v!=p){dfs3(v,u);sz[u]+=sz[v];mx[u]=max(mx[u],sz[v]);}
  mx[u]=max(mx[u],n-sz[u]);                                // "向上"的那棵子树
  if(!ct||mx[u]<mx[ct])ct=u;                               // 重量最小的点即重心(注意 ct 初值)
}
// 16.4 树上差分: 先做修改, 最后一遍 DFS 求子树和还原; O(n + k log n)
int d[N];                                      // 差分数组; 依赖 15.1 的 lca / fa[][]
void add_point(int x,int y,int v){int l=lca(x,y); d[x]+=v; d[y]+=v; d[l]-=v; d[fa[l][0]]-=v;}  // 点差分
void add_edge(int x,int y,int v){int l=lca(x,y); d[x]+=v; d[y]+=v; d[l]-=2*v;}                // 边差分
void dfs4(int u,int p){for(int v:e[u])if(v!=p){dfs4(v,u);d[u]+=d[v];}}  // 自底向上求和还原
// 16.5 欧拉序: DFS 时每到一个点(含回溯)都记录, 长度 2n-1
// pos[u] = u 首次出现的位置; LCA(u,v) = E[pos[u]..pos[v]] 中深度最小的点
int E[2*N],dd[2*N],pos[N],tot;
void dfs5(int u,int p,int d){
  E[++tot]=u; dd[tot]=d; pos[u]=tot;
  for(int v:e[u])if(v!=p){dfs5(v,u,d+1);E[++tot]=u;dd[tot]=d;}}
// 配 ST 表: 预处理 O(n log n), 查询 O(1)

// 17.1 染色判定二分图: O(n+m)。存在奇环 <=> 不是二分图
int col[N];                                    // 0 未染色, 1 / -1 两色
bool dfs(int u,int c){col[u]=c;
  for(int v:e[u]){if(col[v]==c)return false;if(!col[v]&&!dfs(v,-c))return false;}  // 同色 => 奇环
  return true;}
// 主函数: for i if(!col[i] && !dfs(i,1)) { 不是二分图 }  —— 图可能不连通, 每个未染色点都要跑
// 17.2 匈牙利(Kuhn) 二分图最大匹配: O(V*E)
int match[N]; bool vis[N];
bool dfs2(int u){
  for(int v:e[u]){                             // e 只存 左部 -> 右部 的边
    if(vis[v])continue;
    vis[v]=1;
    if(!match[v]||dfs2(match[v])){match[v]=u;return true;}
  }
  return false;
}
int hungary(int n){
  int res=0; memset(match,0,sizeof match);                        // 多测要清 match
  for(int i=1;i<=n;++i){memset(vis,0,sizeof vis);if(dfs2(i))++res;}   // vis 只标记右部, 每轮清空
  return res;}                                 // match 只记"右部匹配到谁", 左部不需要 match

// 17.3 Dinic 最大流: 一般图 O(n^2 m), 单位容量二分图 O(m*sqrt(n))
struct Edge{int to,nxt,cap;} e[M];
int hd[N],cnt=1,dep[N],cur[N],S,T;
void add(int u,int v,int c){e[++cnt]={v,hd[u],c};hd[u]=cnt;e[++cnt]={u,hd[v],0};hd[v]=cnt;}
bool bfs(){                                    // 在残量网络上分层
  memset(dep,0,sizeof dep); queue<int> q; dep[S]=1; q.push(S);
  while(!q.empty()){int u=q.front();q.pop();
    for(int i=hd[u];i;i=e[i].nxt){int v=e[i].to;if(e[i].cap&&!dep[v]){dep[v]=dep[u]+1;q.push(v);}}}
  return dep[T];}
int dfs(int u,int f){                          // 当前弧优化
  if(u==T)return f;
  for(int &i=cur[u];i;i=e[i].nxt){int v=e[i].to;
    if(e[i].cap&&dep[v]==dep[u]+1){int d=dfs(v,min(f,e[i].cap));if(d){e[i].cap-=d;e[i^1].cap+=d;return d;}}}
  return 0;
}
int dinic(){int flow=0,f; while(bfs()){memcpy(cur,hd,sizeof hd);while((f=dfs(S,0x3f3f3f3f)))flow+=f;} return flow;}
// 二分图匹配建模: S->左部容量 1, 右部->T 容量 1, 中间边容量 1, 答案即最大流

// 17.4 费用流(SSP/EK, SPFA 找单位费用最小增广路): 单次 O(nm), 总 O(n*m*f)
struct Edge{int to,nxt,cap,w;} e[M];
int hd[N],cnt=1,dis[N],inq[N],pre[N],pe[N],S,T;
void add(int u,int v,int c,int w){e[++cnt]={v,hd[u],c,w};hd[u]=cnt;e[++cnt]={u,hd[v],0,-w};hd[v]=cnt;}
bool spfa(){
  memset(dis,0x3f,sizeof dis); memset(inq,0,sizeof inq);
  queue<int> q; dis[S]=0; q.push(S); inq[S]=1;
  while(!q.empty()){int u=q.front();q.pop();inq[u]=0;
    for(int i=hd[u];i;i=e[i].nxt){int v=e[i].to;
      if(e[i].cap&&dis[u]+e[i].w<dis[v]){dis[v]=dis[u]+e[i].w;pre[v]=u;pe[v]=i;if(!inq[v])inq[v]=1,q.push(v);}}}
  return dis[T]<0x3f3f3f3f;}
void mcmf(int &flow,int &cost){
  flow=cost=0;
  while(spfa()){int f=0x3f3f3f3f;
    for(int v=T;v!=S;v=pre[v])f=min(f,e[pe[v]].cap);
    for(int v=T;v!=S;v=pre[v]){e[pe[v]].cap-=f;e[pe[v]^1].cap+=f;cost+=f*e[pe[v]].w;}
    flow+=f;}}

// 18.1 差分约束(简述):
// x_i - x_j <= c  =>  加边 j -> i, 权 c, 跑最短路
// x_i - x_j >= c  =>  加边 j -> i, 权 c, 跑最长路(或改写成 x_j - x_i <= -c 跑最短路)
// x_i - x_j == c  =>  上面两条都加
// 超级源点 0 向所有点连权 0 的边, dis[0]=0; 有负环 => 无解, 否则 x_i = dis[i]
// 求最大解跑最短路, 求最小解跑最长路; 用 SPFA 判负环, 最坏 O(nm)
// 18.2 欧拉路径/回路 Hierholzer: O(n+m), 用栈存"回溯点", 答案逆序
int hd[N],to[M],nxt[M],cnt=1;
bool vis[M];
int stk[M],top;
void dfs(int u){
  while(hd[u]){
    int i=hd[u]; hd[u]=nxt[i];                 // 当前弧: 边用完就删
    if(vis[i])continue;
    vis[i]=1; vis[i^1]=1;                      // 无向图: 反向边一起标记
    dfs(to[i]);}
  stk[++top]=u;                                // 回溯时入栈 => 逆序输出
}
// 输出: while(top) printf("%d ", stk[top--]);
// 18.3 基环树: n 点 n 边的连通无向图, 恰好一个环, 环上每点挂一棵树
// 找环(拓扑剥叶): 不断删度为 1 的点, 剩下的就是环上的点
void find_circle(int n){queue<int> q; for(int i=1;i<=n;++i)if(deg[i]==1)q.push(i);
  while(!q.empty()){int u=q.front();q.pop();oncir[u]=false;for(int v:e[u])if(--deg[v]==1)q.push(v);}}
// 基环内向树(每点出度 1): 常配合"跳父亲 + 访问标记"找环, 或直接 Tarjan
// 处理套路: 断环成链 —— 枚举环上一条边 (u,v), 分别"删边"和"强制选边"做两次树形 DP 取最优

// 数字三角形: 自底向上, 一维滚动. O(n^2) 时间, O(n) 空间
for (int j = 1; j <= n; j++) f[j] = a[n][j];          // 最底层
for (int i = n - 1; i >= 1; i--)
  for (int j = 1; j <= i; j++)
    f[j] = max(f[j], f[j + 1]) + a[i][j];             // f[j]/f[j+1] 都是下一层

// 最大子段和: cur = 以当前位置结尾的最大和. O(n)
long long best = -1e18, cur = 0;
for (int i = 1; i <= n; i++)
  cur = max(cur + a[i], (long long)a[i]), best = max(best, cur);

// 方格取数: 两人同时从 (1,1) 走到 (n,n), 同格只算一次
// f[k][i][j]: 走了 k 步, 两人分别在 (i,k-i) 和 (j,k-j). O(n^3)
for (int k = 2; k <= 2 * n; k++)
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int y1 = k - i, y2 = k - j;                       // 行号 -> 列号
      if (y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue;
      long long add = (i == j) ? a[i][y1] : a[i][y1] + a[j][y2];
      f[k & 1][i][j] = max(max(f[~k & 1][i][j], f[~k & 1][i-1][j]),
                           max(f[~k & 1][i][j-1], f[~k & 1][i-1][j-1])) + add;
    }

// 01 背包: f[j] = 容量 j 的最大价值; 体积 w[i], 价值 v[i]. O(nW)
// 至多 W: 全部初始化为 0; 恰好装满: f[0]=0, 其余 -INF
const long long NEG = -0x3f3f3f3f3f3f3f3fLL;
for (int j = 0; j <= W; j++) f[j] = (j == 0 ? 0 : NEG);   // 恰好装满
for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)                          // 必须逆序!
    f[j] = max(f[j], f[j - w[i]] + v[i]);

// 完全背包: 每件无限个, 容量正序. O(nW)
for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);

// 多重背包: 第 i 件有 c0[i] 个, 拆成 1,2,4,...,余数 后做 01 背包
// O(W * sum log c[i])
int idx = 0;
for (int i = 1; i <= n; i++) {
  int c = c0[i];
  for (int k = 1; k <= c; k <<= 1) { c -= k; ww[++idx] = k * w[i]; vv[idx] = k * v[i]; }
  if (c) { ww[++idx] = c * w[i]; vv[idx] = c * v[i]; }
}
for (int i = 1; i <= idx; i++)
  for (int j = W; j >= ww[i]; j--) f[j] = max(f[j], f[j - ww[i]] + vv[i]);

// 多重背包 · 单调队列优化. O(nW); 队列存 (值, 下标 k)
for (int i = 1; i <= n; i++) {
  for (int r = 0; r < w[i] && r <= W; r++) {              // 按余数分组
    int L = 0, R = -1;
    for (int k = 0; r + k * w[i] <= W; k++) {
      int j = r + k * w[i];
      long long cur = f[j] - 1LL * k * v[i];
      while (L <= R && q[R].first <= cur) R--;            // 单调队列
      q[++R] = {cur, k};
      while (q[L].second < k - c0[i]) L++;                // 超出个数限制
      f[j] = q[L].first + 1LL * k * v[i];
    }
  }
}

// 分组背包: 第 k 组有 cnt[k] 件物品 (Wk[t], Vk[t]). O(W * sum cnt)
for (int k = 1; k <= ts; k++)
  for (int j = W; j >= 0; j--)                            // 容量在外
    for (int t = 0; t < cnt[k]; t++)                      // 组内物品在内
      if (j >= Wk[k][t]) f[j] = max(f[j], f[j - Wk[k][t]] + Vk[k][t]);

// 金明式依赖 -> 分组背包: plan[k] 预存组内所有 (费用, 价值) 方案. O(W * sum |plan[k]|)
for (int k = 1; k <= ts; k++)
  for (int j = W; j >= 0; j--)
    for (auto &pr : plan[k])
      if (j >= pr.first) f[j] = max(f[j], f[j - pr.first] + pr.second);

// 方案数: 把 max 换成加法, 初值 dp[0] = 1. O(nW)
dp[0] = 1;
for (int i = 1; i <= n; i++)                   // 01: 逆序, 每件用一次
  for (int j = W; j >= w[i]; j--) dp[j] += dp[j - w[i]];
for (int i = 1; i <= n; i++)                   // 完全: 正序, 每件无限
  for (int j = w[i]; j <= W; j++) dp[j] += dp[j - w[i]];
// 答案: 恰好装满 -> dp[W]; 至多 -> sum_{j<=W} dp[j]