Editorial — Codeguerra

Notice that the rift at index $$$n$$$ is always stable, because $$$a_n \le n$$$ for every possible value.

$$$n$$$ can be as large as $$$10^{18}$$$. Do we really need to compute factorial up to that value? Think about the modulus $$$69696$$$

We want arrays where after choosing exactly one index $$$i$$$ and setting $$$a_i=i$$$, there is exactly one stable rift ($$$a_i \le i$$$).

All other positions must be unstable $$$\Rightarrow a_j \gt j$$$.

Since position n is always stable eleven has no choice but to chose it. There are total of n different values for last index $$$\rightarrow n$$$ ways.

Number of choices for rest:

• Index 1 $$$\rightarrow (n-1)$$$ choices
• Index 2 $$$\rightarrow (n-2)$$$ choices
• $$$\dots$$$
• Index $$$n-1 \rightarrow 1$$$ choice

Total arrays $$$= n \cdot (n-1)(n-2)\cdots 1 = n!$$$.

Compute $$$n! \bmod 69696$$$. Since $$$69696 \mid n!$$$ for $$$n \ge 22$$$, the answer is $$$0$$$ for $$$n \ge 22$$$.

Time Complexity: $$$O(1)$$$ per test Space Complexity: $$$O(22)$$$

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

typedef long long ll;

ll fac[25];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    fac[0] = 1;
    for(int i = 1; i < 25; ++i){
        fac[i] = fac[i - 1] * i;
    }

    ll tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;

        // nth element always stable
        // so rest has to be unstable
        // total ways = n!

        if(n >= 22){
            cout << 0 << '\n';
        } else {
            cout << fac[n] << '\n';
        }
    }

    return 0;
}

Core Logic: Chicken McNugget Theorem
By the Chicken McNugget Theorem (Frobenius Coin Problem), for any equation $$$ax+by=c$$$ with coprime $$$a, b$$$, the largest integer that cannot be expressed using non-negative integers $$$x, y$$$ is $$$ab - a - b$$$.
Intuitively, this logic extends to any pair $$$(a, b)$$$ with $$$\gcd(a, b) = g$$$, where the pattern becomes regular (periodic) for multiples of $$$g$$$ after the limit $$$\frac{ab}{g} - a - b$$$.

Approach:

• Brute Force (The "Irregular" Head):
Since we know the reachability becomes predictable after $$$Limit = \frac{ab}{g} - a - b$$$, we can simply brute-force (using a boolean array or DP) for all values up to this limit.
  • Why this works: The problem guarantees $$$\sum a_i b_i \le 5 \cdot 10^6$$$. Since the limit is strictly less than $$$ab$$$, the total operations for this brute-force step across all test cases will never exceed the time limit.
    
• Prefix Sum (The "Periodic" Tail):
Once we pass the calculated limit, the jammer will reinforce every multiple of $$$g$$$.
We store the starting point ($$$Start \gt Limit$$$) for each jammer grouped by their $$$g$$$.
To calculate the total jammers for these large values efficiently, we use a harmonic sweep:
  • For each GCD value $$$g$$$, let count be an array tracking active jammers.
  • Initialize count[start]++ for every jammer starting at start.
  • Apply a stride-based prefix sum: Iterate $$$j$$$ from $$$g$$$ to $$$N$$$ with step $$$g$$$, updating count[j+g] += count[j].
  • This propagates the number of active jammers through all subsequent multiples of $$$g$$$.

Time Complexity:

• Part 1 (DP): $$$O(\sum a_i b_i)$$$. Given the constraint $$$\sum a_i b_i \le 5 \cdot 10^6$$$, this is extremely fast (~0.05 seconds).
  
• Part 2 (Harmonic Sweep): We iterate through multiples for each $$$g$$$. This follows the harmonic series $$$N/1 + N/2 + \dots + N/N$$$, which sums to $$$O(N \log N)$$$. With $$$N=2 \cdot 10^5$$$, this is roughly $$$3 \cdot 10^6$$$ operations. Total Complexity: $$$O(\sum a_i b_i + N \log N)$$$.

#include <bits/stdc++.h>
using namespace std;
void run(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
 
#define ll long long
#define pb push_back
 
ll gcd(ll a, ll b) {while (b) {ll temp = b;b = a % b;a = temp;}return a;}
ll lcm(ll a, ll b) {if(a==0||b==0)return 0; return (a/gcd(a,b))*b;}
 
void fun(){
    ll n, k;
    cin >> n >> k;
 
    vector<ll> ans1(n+1, 0), ans(n+1, 0);
    vector<vector<ll>> vals(n+1);
 
    for(int i=1; i<=k; i++){
        ll a, b; cin >> a >> b;
        ll g = gcd(a, b);
 
        // Calculate limit safely
        ll limit_val = (a*b)/g - a - b;
        ll limit = min(n, limit_val);
 
        vector<bool> dp(max(0LL, limit) + 1, 0);
        dp[0] = 1;
 
        for(int j=0; j<=limit; j++){
            if(dp[j]) {
                if(j > 0) ans1[j]++; // Update Head count
                if(j+a <= limit) dp[j+a] = 1;
                if(j+b <= limit) dp[j+b] = 1;
            }
        }
 
        // Calculate Tail start
        // Ensure start is at least g (index 1-based, multiples of g)
        ll start = max(g, (limit/g)*g + g);
 
        if(start <= n) vals[g].pb(start);
    }
 
    // Merge Head counts
    for(int i=1; i<=n; i++) ans[i] += ans1[i];
 
    // Harmonic Sweep for Tail
    vector<ll> curr(n+1, 0);
    for(int i=1; i<=n; i++){
        if(vals[i].empty()) continue;
 
        for(auto it : vals[i]) curr[it]++;
 
        for(int j=i; j<=n; j+=i){
            if(curr[j] > 0) ans[j] += curr[j];
            if(j+i <= n) curr[j+i] += curr[j];
        }
        // Cleanup
        for(int j=i; j<=n; j+=i) curr[j] = 0LL;
    }
 
    for(int i=1; i<=n; i++) cout << ans[i] << (i==n ? "" : " ");
    cout << "\n";
}
 
int main(){
    run();
    ll t; cin >> t;
    while(t--) fun();
}

Think of the gain from one operation as $$$ gain = \sum_{k=l_2}^{r_2} b_k - \sum_{k=l}^{r} a_k, $$$ with $$$(l \le l_2 \le r_2 \le r)$$$.

Rearrange using prefix sums: $$$ gain = (pref_b[r_2]-pref_b[l_2-1]) + (pref_a[l-1]-pref_a[r]). $$$

So while scanning rightwards you should keep best values of expressions like $$$(pref_a[l-1])$$$ and $$$(-pref_b[l_2-1]+pref_a[l-1])$$$ to build the optimal gain.

You can compute the maximum gain with a single left→right pass using 4 DP maxima:

• dp1[i] = max pref_a[0..i] — dp2[i] = max(dp2[i-1], -pref_b[i]+dp1[i]) — dp3[i] = max(dp3[i-1], dp2[i]+pref_b[i]) — dp4[i] = max(dp4[i-1], dp3[i]-pref_a[i])

The final answer is sum(a) + dp4[n].

Precompute prefix sums pref and prefb.

Use four DP arrays to maintain best intermediate expressions (see hints). dp4[n] is the maximum extra sum achievable by removing some A[l..r] and inserting some B[l2..r2] with $$$(l \le l_2 \le r_2 \le r)$$$ (empty subarrays allowed).

The answer is sum(A) + dp4[n].

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

typedef long long ll;

/* read vector */
void readVector(vector<ll>& v){
    for(size_t i = 0; i < v.size(); ++i){
        cin >> v[i];
    }
}

/* prefix sum: pref[i] = sum of first i elements (1-indexed logic) */
vector<ll> prefix(const vector<ll>& v){
    int n = v.size();
    vector<ll> pref(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        pref[i] = pref[i - 1] + v[i - 1];
    }
    return pref;
}

/* sum of vector */
ll sumV(const vector<ll>& v){
    ll s = 0;
    for(ll x : v) s += x;
    return s;
}

void resolve2(ll tc){
    int n;
    cin >> n;

    vector<ll> a(n);
    readVector(a);

    vector<ll> b(n);
    readVector(b);

    /*
        max(pref[r2]-pref[l2-1]-(pref[r]-pref[l-1]))
        l <= l2 <= r2 <= r
        transformed DP:
        max(-pref[r] + pref[r2] + pref[l-1] - pref[l2-1])
    */

    vector<ll> pref = prefix(a);
    vector<ll> prefb = prefix(b);

    vector<ll> dp1(n + 1, 0); // max pref[l-1]
    vector<ll> dp2(n + 1, 0); // max -prefb[i] + dp1[i]
    vector<ll> dp3(n + 1, 0); // max dp2[j] + prefb[j]
    vector<ll> dp4(n + 1, 0); // max dp3[j] - pref[j]

    for(int i = 1; i <= n; ++i){
        dp1[i] = max(dp1[i - 1], pref[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp2[i] = max(dp2[i - 1], -prefb[i] + dp1[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp3[i] = max(dp3[i - 1], dp2[i] + prefb[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp4[i] = max(dp4[i - 1], dp3[i] - pref[i]);
    }

    ll totSum = sumV(a);
    cout << totSum + dp4[n] << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll tc;
    cin >> tc;
    while(tc--){
        resolve2(tc);
    }
    return 0;
}

The maximum strength of a connection between two chambers depends only on the maximum GCD achievable between one element from each chamber. You do not need to consider all possible pairs.

A chamber can participate in an edge of weight g if it contains at least one number divisible by g. Use this to group chambers by divisors instead of building all possible edges.

To maximize the total strength, process the groups in descending order of GCD and connect chambers greedily using a Disjoint Set Union (DSU) structure, similar to Kruskal's algorithm for Maximum Spanning Trees.

We want to connect all psychic chambers into a single network with maximum total strength. Since the network must be connected and acyclic, this is a Maximum Spanning Tree problem.

For any two chambers, the best edge between them is the maximum GCD achievable between their elements. We do not need to explicitly build all edges.

Approach:

• For every value v, store all chambers that contain v.
• Iterate over all possible GCD values g from largest to smallest.
• For a fixed g, iterate over all multiples of g and collect all chambers that contain those values.
• Any two such chambers can be connected with an edge of weight at least g.
• Use Disjoint Set Union (DSU) to greedily connect these chambers. Each successful merge adds g to the total answer.

Processing GCDs in descending order ensures that the first time two components are connected, they are connected using their maximum possible GCD. DSU guarantees no cycles and exactly N-1 edges.

This greedy procedure is equivalent to Kruskal's algorithm for Maximum Spanning Tree and produces the optimal result.

Time Complexity: Enumerating multiples follows a harmonic series, giving O(M log M), where M = 2 * 10^5.

Space Complexity: O(N + sum(k_i))

#include <bits/stdc++.h>
using namespace std;
 
// Disjoint Set Union structure for maintaining connected components
struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n,1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]); // path compression
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false; // already connected
        if(sz[a] < sz[b]) swap(a,b); // union by size
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
 
        const int MAXV = 200000;
        vector<vector<int>> pos(MAXV + 1); // pos[x] = list of chambers containing value x
 
        // Read chambers and store positions for each value
        for(int i = 0; i < N; i++){
            int k;
            cin >> k;
            while(k--){
                int x;
                cin >> x;
                pos[x].push_back(i);
            }
        }
 
        DSU dsu(N);
        long long ans = 0;
 
        vector<int> nodes;
        // Process all possible gcd values from largest to smallest
        for(int g = MAXV; g >= 1; g--){
            nodes.clear();
            // Gather all chambers containing multiples of g
            for(int m = g; m <= MAXV; m += g){
                for(int v : pos[m]){
                    nodes.push_back(v);
                }
            }
            if(nodes.empty()) continue;
 
            // Connect all gathered chambers with edges of weight g
            int root = nodes[0];
            for(int i = 1; i < (int)nodes.size(); i++){
                if(dsu.unite(root, nodes[i])){
                    ans += g; // add edge weight to total
                }
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}
 

Since every node in the initial tree has a degree at most $$$k$$$, a node only becomes a Focus Point if its degree remains exactly $$$k$$$. To minimize the number of chambers destroyed, we need to find the largest possible connected subgraph (a tree) that contains exactly one node with degree $$$k$$$ and all other nodes with degree $$$ \lt k$$$.

Define $$$a[u]$$$ as the maximum size of a "clean" subtree rooted at $$$u$$$ (where no node in that subtree has degree $$$k$$$). If the current node $$$u$$$ has degree $$$k$$$ within the subtree, you must prune the smallest child branch to reduce its degree to $$$k-1$$$ and keep the subtree "clean."

To satisfy the "exactly one Focus Point" rule, you can "restore" one pruned branch. If you restore the branch we pruned from node $$$i$$$, that branch size is $$$b[i]$$$. The total size becomes the "clean" tree size plus this restoration gain.

We want to find the largest possible connected network such that exactly one node has degree $$$k$$$ and all others have degree $$$ \lt k$$$. Key Observation: Because every node in the initial tree has $$$degree \le k$$$, we only need to worry about nodes having a degree of exactly $$$k$$$. To "fix" a node with degree $$$k$$$, we must remove at least one of its edges.

Approach (Tree DP with Restoration):

• DP State $$$a[u]$$$: The maximum number of nodes in a connected component rooted at $$$u$$$ such that $$$u$$$ and all its descendants have $$$degree \lt k$$$.
• Pruning Logic:
  • If $$$deg(u) \lt k$$$, $$$a[u] = 1 + \sum a[v]$$$.
  • If $$$deg(u) = k$$$, $$$a[u] = 1 + (\sum a[v]) - \min(a[v])$$$. We store the pruned value in $$$b[u] = \min(a[v])$$$.
• Focus Point Restoration:
  • While traversing, we use add to track the best focus point found in subtrees below us where the connection to the parent is already broken.
  • We update ans = max(ans, current_total_clean_size + add) to handle focus points in isolated subtrees.
  • After the DFS, we check if node 1 or any other node $$$i$$$ can be the restored Focus Point using max(ans, a[1] + b[i]).

Correctness Proof:The DP correctly calculates the maximum size of a "clean" tree. By returning the maximum of the internal subtree focus points (add) and the pruned branch size (mini), we ensure that we consider every possible node as a potential Focus Point exactly once while maintaining connectivity.

Time Complexity:

• Tree Traversal: $$$O(N)$$$ because each node and edge is visited a constant number of times during the DFS.
• Final Scan: $$$O(N)$$$ to iterate through the restoration array $$$b$$$.

Space Complexity: $$$O(N)$$$ to store the adjacency list and DP arrays $$$a$$$ and $$$b$$$.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define vi vector<int>
#define graph vector<vector<int>>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
// solve returns the best focus point bonus (restored branch) found in the subtree
int solve(int parent, int node, int& ans, graph& adj, vi& a, vi& b, int k) {
    if (adj[node].size() == 1 && parent != -1) {
        a[node] = 1;
        return 0;
    }
 
    int sum = 0;
    int mini = LLONG_MAX;
    int add = 0;
 
    for (auto child : adj[node]) {
        if (child != parent) {
            add = max(add, solve(node, child, ans, adj, a, b, k));
            sum += a[child];
            mini = min(mini, a[child]);
        }
    }
 
    if (adj[node].size() < k) {
        a[node] = sum + 1;
        return add;
    }
 
    // Node currently has degree k.
    // Calculate size if this node is chosen to be the Focus Point.
    int size_if_focus = sum + 1;
    ans = max(ans, size_if_focus + add);
 
    // To keep the subtree "clean" for the parent, we prune the smallest branch.
    a[node] = sum - mini + 1;
    b[node] = mini;
 
    // Return the best focus point candidate: either one from below or this node's pruned branch.
    return max(add, mini);
}
 
void solve_test_case() {
    int n, k;
    if (!(cin >> n >> k)) return;
    graph adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == k) count++;
    }
 
    // If only one or zero focus points exist, no chambers need to be destroyed.
    if (count <= 1) {
        cout << 0 << endl;
        return;
    }
 
    vi a(n + 1, 0), b(n + 1, 0);
    int ans = 0;
 
    // Start DFS from node 1.
    for (auto child : adj[1]) {
        solve(1, child, ans, adj, a, b, k);
    }
 
    int sum = 0;
    int mini = LLONG_MAX;
    for (auto child : adj[1]) {
        sum += a[child];
        mini = min(mini, a[child]);
    }
 
    a[1] = sum + 1;
    if (adj[1].size() == k) {
        a[1] -= mini;
        b[1] = mini;
    }
 
    ans = max(ans, a[1]);
 
    // Final check: what if node i is the restored Focus Point in node 1's component?
    for (int i = 1; i <= n; i++) {
        ans = max(ans, a[1] + b[i]);
    }
 
    cout << n - ans << endl;
}
 
int32_t main() {
    fastio;
    int t;
    cin >> t;
    while (t--) {
        solve_test_case();
    }
    return 0;
}

Sort the manual activations array and iterate each manual activation in order computing automatic activations inbetween.

Remember to use int64 datatype (long long) since $$$n*x$$$ can reach upto $$$10^{18}$$$.

Keep track of the last end time of the alarm to avoid double-counting overlapping intervals.

For automatic activations, note that after a trigger at time $$$t$$$, the next useful activation is at $$$time \gt t + k$$$. This allows you to skip multiple automatic activations at once.

Approach Overview

The key is to simulate the alarm efficiently without iterating over all automatic activations individually. First, sort all manual arrival times. Maintain last — the time until which the last alarm was active. For each manual arrival time, calculate how many automatic activations are already covered and whether a new interval needs to be added. Use the fact that automatic activations occur at regular intervals to batch-process multiple activations in constant time. Finally, handle any remaining automatic activations after the last manual arrival.

Detailed Solution

1) Sorting and Initialization
Sort the manual arrival times v to process events chronologically. Initialize two variables — last = 0 to track the end of the current active interval and ans = 0 to track the number of active intervals.

2) Processing Each Manual Arrival
For each arrival time t, call update(t) which:

• Compute the number of automatic activations before the previous last (curr = last / x) and before or equal to current time t (next = t / x).
• Determine how many automatic activations are not yet covered and would start a new interval.
• The step = 1 + k/x represents the minimum gap of automatic triggers required to start a new interval without overlap.
• Update last to the end time of the last activation and increment ans for each new interval.
• After this, if the current last does not cover t, manually trigger a new interval ending at t + k and increment ans.

3) Final Automatic Activation
After processing all manual arrivals, call update(n*x) to account for any remaining automatic activations up to time $$$n*x$$$.

Finally compute the total time. Since each interval contributes exactly k seconds, so the total active time is: ans * k

Complexity Analysis
Sorting the manual arrivals: $$$O(m * log m)$$$
Processing manual and automatic events: $$$O(m)$$$
Overall: $$$O(m * log m)$$$

#include <bits/stdc++.h> 
using namespace std;
 
#define ll long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL)
 
//covers all automatic and a manual before (and equal to) time t
void update(ll t, ll x, ll k, ll &last, ll &ans){
    ll prev = last/x; //previous count of automatic triggers completed
    ll curr = t/x;//new count of automatic triggers completed
 
    ll cnt = 0;
 
    //covers all automatic before and equal to t
    if(curr-prev > 0){
        //minimum gap of automatic triggers required to start a new interval without overlap.
        ll step = 1 + (k/x);
 
        cnt += (curr-prev+step-1)/step;
 
        ll lastcomplete = curr - (curr-prev-1)%step;
        last = lastcomplete*x + k;
    }
 
    //if the last automatic does not cover the t then handle it separately
    if(last < t){
        last = t + k;
        cnt++;
    }
 
    ans += cnt;
}
 
int main() {
    fastio();
 
    int t = 1;
    // cin>>t;
    while(t--){
        ll n,m,x,k;
        cin >> n >> x >> k >> m;
 
        vector<long long> v(m);
        for(auto &val: v) cin >> val;
 
        sort(v.begin(), v.end());
 
        ll last = 0, ans = 0;
 
        for(int i=0; i<m; i++){
            update(v[i], x, k, last, ans);
        }
 
        //handle remaining automatics
        update(n*x, x, k, last, ans);
 
        cout << (ans*k) << endl;
    }
    return 0;
}

First solve the classic LeetCode Cat and Mouse problem (retrograde/BFS on game states): Cat And Mouse.

Model each game state as a 4-tuple (m_pos, v_pos, mask, turn)

where: — m_pos = Max’s node, — v_pos = Vecna’s node (never 1), — mask = bitmask of rescued children (0..(1<<k)-1), — turn = 0 (Max to move) or 1 (Vecna to move).

This problem is solved exactly like the Cat and Mouse game using retrograde BFS on game states.

The only difference is that when Max visits a node containing a child, we update the mask. Since k ≤ 5, the mask has at most 2^k ≤ 32 possibilities, which is small.

So we just multiply the original Cat & Mouse state space by 32 to track children — everything else stays the same. Time Complexity: $$$ O(n * n * 2^k) $$$ With $$$( n \le 50 , k \le 5 )$$$, this is at most about 160k states, each processed in constant/degree time.

Space Complexity: $ O(n * n * 2^k). for storing outcomes and degrees. Both comfortably fit within limits.

#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;

const int MAXN = 51;
const int MAXK = 32;

int n, m, k;
vector<int> adj[MAXN];
int child_node[MAXN]; // -1 if no child, else 0..k-1
int outcome[MAXN][MAXN][MAXK][2]; // 0: DRAW, 1: MAX, 2: VECNA
int degree[MAXN][MAXN][MAXK][2];

struct State {
    int m_pos, v_pos, mask, turn;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cin >> k;
    for (int i = 1; i <= n; ++i) child_node[i] = -1;
    for (int i = 1; i <= n; ++i) {
        int c; cin >> c;
        if (c != -1) child_node[i] = c;
    }

    queue<State> q;

    // 1. Initialize Degrees and Win/Loss States
    for (int mp = 1; mp <= n; ++mp) {
        for (int vp = 2; vp <= n; ++vp) { // Vecna never at 1
            for (int mask = 0; mask < (1 << k); ++mask) {
                // Max's Turn (0)
                degree[mp][vp][mask][0] = adj[mp].size();
                
                // Vecna's Turn (1)
                for (int next_v : adj[vp]) {
                    if (next_v != 1) degree[mp][vp][mask][1]++;
                }

                // Terminal Condition: Vecna catches Max
                // This happens if Vecna moves to Max, or Max moves to Vecna.
                if (mp == vp) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 2; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 2; q.push({mp, vp, mask, 1}); }
                }
                // Terminal Condition: Max reaches cave with all children
                else if (mp == 1 && mask == (1 << k) - 1) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 1; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 1; q.push({mp, vp, mask, 1}); }
                }
            }
        }
    }

    // 2. Retrograde Propagation
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        int res = outcome[curr.m_pos][curr.v_pos][curr.mask][curr.turn];

        if (curr.turn == 1) { // Current is Vecna, Predecessor was Max
            for (int prev_m : adj[curr.m_pos]) {
                // To reach 'curr.mask' at 'curr.m_pos', Max must have had 'prev_mask'
                // at 'prev_m'. 
                for (int prev_mask = 0; prev_mask < (1 << k); ++prev_mask) {
                    int next_mask = prev_mask;
                    if (child_node[curr.m_pos] != -1) next_mask |= (1 << child_node[curr.m_pos]);
                    
                    if (next_mask == curr.mask) {
                        if (outcome[prev_m][curr.v_pos][prev_mask][0]) continue;

                        if (res == 1) { // Max found a move to win
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 1;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        } else if (--degree[prev_m][curr.v_pos][prev_mask][0] == 0) {
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 2;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        }
                    }
                }
            }
        } else { // Current is Max, Predecessor was Vecna
            for (int prev_v : adj[curr.v_pos]) {
                if (prev_v == 1) continue;
                if (outcome[curr.m_pos][prev_v][curr.mask][1]) continue;

                if (res == 2) { // Vecna found a move to win
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 2;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                } else if (--degree[curr.m_pos][prev_v][curr.mask][1] == 0) {
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 1;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                }
            }
        }
    }

    // 3. Result
    int start_mask = 0;
    if (child_node[2] != -1) start_mask |= (1 << child_node[2]);
    cout << outcome[2][3][start_mask][0] << endl;

    return 0;
}