When does the game end?

Depending on whether the player chooses to exchange wallets with their opponent on step $$$1$$$, $$$1$$$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.

The only way that the game ends is when both players have $$$0$$$ coins. Since each operation decreases the total amount of coins by exactly $$$1$$$, the only way for Alice to win the game is if $$$a + b$$$ is odd.

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

int main() {
    int t; cin >> t;
    while (t--) {
        int a, b; cin >> a >> b;
        if ((a + b) % 2 == 0) {
            cout << "Bob\n";
        } else {
            cout << "Alice\n";
        }
    }
}

Try to find a lower bound.

The answer is $$$|a_1 + a_2 + \ldots + a_n|$$$. Intuitively, whenever we have a subarray with a sum equal to $$$0$$$, it will be helpful for us as its penalty will become $$$0$$$. Hence, we can split $$$a$$$ into subarrays with a sum equal to $$$0$$$ and group up the remaining elements into individual subarrays of size $$$1$$$. A formal proof is given below.

Let us define an alternative penalty function $$$p2(l, r) = |a_l + a_{l+1} + \ldots + a_r|$$$. We can see that $$$p2(l, r) \le p(l, r)$$$ for all $$$1\le l\le r\le n$$$. Since the alternative penalty function does not have the $$$(r - l + 1)$$$ term, there is no reason for us to partition $$$a$$$ into two or more subarrays as $$$|x| + |y| \ge |x + y|$$$ for all integers $$$x$$$ and $$$y$$$, so the answer for the alternative penalty function is $$$|a_1 + a_2 + \ldots + a_n|$$$.

Since $$$p2(l, r)\le p(l, r)$$$, this means that the answer to our original problem cannot be smaller than $$$|a_1 + a_2 + \ldots + a_n|$$$. In fact, this lower bound is always achievable. Let us prove this by construction.

Note that if we flip every "$$$\mathtt{+}$$$" to "$$$\mathtt{-}$$$" and every "$$$\mathtt{-}$$$" to "$$$\mathtt{+}$$$", our answer will remain the same since our penalty function involves absolute values. Hence, we can assume that the sum of elements of $$$a$$$ is non-negative.

If the sum of elements of $$$a$$$ is $$$0$$$, we can split $$$a$$$ into a single array equal to itself $$$b_1 = a$$$ and obtain a penalty of $$$0$$$. Otherwise, we find the largest index $$$i$$$ where $$$a_1 + a_2 + \ldots + a_i = 0$$$. Then we let the first subarray be $$$b_1 = [a_1, a_2, \ldots, a_i]$$$ and the second subarray be $$$b_2 = [a_{i + 1}]$$$, so we have $$$p(b_1) = 0$$$ and $$$p(b_2) = 1$$$. Since $$$i$$$ is the largest index, $$$a_{i + 1}$$$ has to be equal to $$$1$$$ as if $$$a_{i + 1}$$$ is $$$-1$$$ instead, there has to be a larger index where the prefix sum becomes $$$0$$$ again for the prefix sum to go from negative to the final positive total sum. This means that for the remaining elements of the array $$$a_{i+2\ldots n}$$$, the sum of its elements decreases by $$$1$$$, so we can continue to use the same procedure to split the remaining elements which decrease the sum by $$$1$$$ and increase the penalty by $$$1$$$ each time until the sum of elements becomes $$$0$$$. Hence, the total penalty will be equal to the sum of elements of $$$a$$$.

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

int t;
int n;
string s;

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> s;
        int sm = 0;
        for (int i = 0; i < n; i++) {
            sm += s[i] == '+' ? 1 : -1;
        }
        cout << abs(sm) << '\n';
    }
}

Consider a greedy approach.

Consider the following approach. We start with empty arrays $$$b$$$ and $$$c$$$, then insert elements of the array $$$a$$$ one by one to the back of $$$b$$$ or $$$c$$$. Our penalty function only depends on adjacent elements, so at any point in time, we only care about the value of the last element of arrays $$$b$$$ and $$$c$$$. Suppose we already inserted $$$a_1, a_2, \ldots, a_{i - 1}$$$ into arrays $$$b$$$ and $$$c$$$ and we now want to insert $$$a_i$$$. Let $$$x$$$ and $$$y$$$ be the last element of arrays $$$b$$$ and $$$c$$$ respectively (if they are empty, use $$$\infty$$$). Note that swapping arrays $$$b$$$ and $$$c$$$ does not matter, so without loss of generality, assume that $$$x\le y$$$. We will use the following greedy approach.

1. If $$$a_i\le x$$$, insert $$$a_i$$$ to the back of the array with a smaller last element.
2. If $$$y \lt a_i$$$, insert $$$a_i$$$ to the back of the array with a smaller last element.
3. If $$$x \lt a_i\le y$$$, insert $$$a_i$$$ to the back of the array with a bigger last element.

The proof of why the greedy approach is optimal is given below:

1. $$$a_i\le x$$$. In this case, $$$a_i$$$ is not greater than the last element of both arrays, so inserting $$$a_i$$$ to the back of either array will not add additional penalties. However, it is better to insert $$$a_i$$$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
2. $$$y \lt a_i$$$. In this case, $$$a_i$$$ is greater than the last element of both arrays, so inserting $$$a_i$$$ to the back of either array will contribute to $$$1$$$ additional penalty. However, it is better to insert $$$a_i$$$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
3. $$$x \lt a_i\le y$$$. In this case, if we insert $$$a_i$$$ to the back of the array with the larger last element, there will not be any additional penalty. However, if we insert $$$a_i$$$ to the back of the array with the smaller last element, there will be an additional penalty of $$$1$$$. The former option is always better than the latter. This is because if we consider making the same choices for the remaining elements $$$a_{i+1}$$$ to $$$a_n$$$ in both scenarios, there will be at most one time where the former scenario will add one penalty more than the latter scenario as the former scenario has a smaller last element after inserting $$$a_i$$$. After that happens, the back of the arrays in both scenarios will become the same and hence, the former case will never be less optimal.

Following the greedy approach for all 3 cases will result in a correct solution that runs in $$$O(n)$$$ time.

Consider a dynamic programming approach.

Let $$$dp_{i, v}$$$ represent the minimum penalty when we are considering splitting $$$a_{1\ldots i}$$$ into two subarrays where the last element of one subarray is $$$a_i$$$ while the last element of the second subarray is $$$v$$$.

Speed up the transition by storing the state in a segment tree.

Let us consider a dynamic programming solution. Let $$$dp_{i, v}$$$ represent the minimum penalty when we are considering splitting $$$a_{1\ldots i}$$$ into two subarrays where the last element of one subarray is $$$a_i$$$ while the last element of the second subarray is $$$v$$$. Then, our transition will be $$$dp_{i, v} = dp_{i - 1, v} + [a_{i - 1} \lt a_i]$$$ for all $$$1\le v\le n, v\neq a_{i - 1}$$$ and $$$dp_{i, a_{i - 1}} = \min(dp_{i - 1, a_{i - 1}} + [a_{i - 1} \lt a_i], \min_{1\le x\le n}(dp_{i - 1, x} + [x \lt a_i]))$$$.

To speed this up, we use a segment tree to store the value of $$$dp_{i - 1, p}$$$ at position $$$p$$$. To transition to $$$dp_i$$$, notice that the first transition is just a range increment on the entire range $$$[1, n]$$$ of the segment tree if $$$a_{i - 1} \lt a_i$$$. For the second transition, we can do two range minimum queries on ranges $$$[1, a_i - 1]$$$ and $$$[a_i, n]$$$. The final time complexity is $$$O(n\log n)$$$.

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

const int INF = 1000000005;
const int MAXN = 200005;

int t;
int n;
int a[MAXN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int t1 = INF, t2 = INF;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (t1 > t2) {
                swap(t1, t2);
            }
            if (a[i] <= t1) {
                t1 = a[i];
            } else if (a[i] <= t2) {
                t2 = a[i];
            } else {
                t1 = a[i];
                ans++;
            }
        }
        cout << ans << '\n';
    }
}

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

const int INF = 1000000005;
const int MAXN = 200005;

int t;
int n;
int a[MAXN];

int mn[MAXN * 4], lz[MAXN * 4];
void init(int u = 1, int lo = 1, int hi = n) {
    mn[u] = lz[u] = 0;
    if (lo != hi) {
        int mid = lo + hi >> 1;
        init(u << 1, lo, mid);
        init(u << 1 ^ 1, mid + 1, hi);
    }
}
void propo(int u) {
    if (lz[u] == 0) {
        return;
    }
    lz[u << 1] += lz[u];
    lz[u << 1 ^ 1] += lz[u];
    mn[u << 1] += lz[u];
    mn[u << 1 ^ 1] += lz[u];
    lz[u] = 0;
}
void incre(int s, int e, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        mn[u] += x;
        lz[u] += x;
        return;
    }
    propo(u);
    int mid = lo + hi >> 1;
    if (s <= mid) {
        incre(s, e, x, u << 1, lo, mid);
    }
    if (e > mid) {
        incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    }
    mn[u] = min(mn[u << 1], mn[u << 1 ^ 1]);
}
int qmn(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (s > e) {
        return INF;
    }
    if (lo >= s && hi <= e) {
        return mn[u];
    }
    propo(u);
    int mid = lo + hi >> 1;
    int res = INF;
    if (s <= mid) {
        res = min(res, qmn(s, e, u << 1, lo, mid));
    }
    if (e > mid) {
        res = min(res, qmn(s, e, u << 1 ^ 1, mid + 1, hi));
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        init();
        for (int i = 1; i <= n; i++) {
            int ndp = min(qmn(1, a[i] - 1) + 1, qmn(a[i], n));
            if (i > 1) {
                if (a[i - 1] < a[i]) {
                    incre(1, n, 1);
                }
                int dp = qmn(a[i - 1], a[i - 1]);
                if (ndp < dp) {
                    incre(a[i - 1], a[i - 1], ndp - dp);
                }
            }
        }
        cout << qmn(1, n) << '\n';
    }
}

Solve the problem if you have to split the array into $$$k$$$ subsequences, where $$$k$$$ is given in the input ($$$k = 2$$$ for the original problem).

What does the distance of two leaves that share the same parent look like?

What happens if we delete two leaves that share the same parent?

Consider two leaves that share the same parent. They will be adjacent to each other in the dfs order, so their distances will be adjacent in array $$$a$$$. Furthermore, their distances to the root will differ by exactly $$$1$$$ since one of the edges from the parent to its children will have weight $$$0$$$ while the other will have weight $$$1$$$.

If we delete two leaves that share the same parent, the parent itself will become the leaf. Since one of the edges from the parent to the child has weight $$$0$$$, the distance from the parent to the root is equal to the smaller distance between its two children. This means that deleting two leaves that share the same parent is the same as selecting an index $$$i$$$ such that $$$a_i = a_{i - 1} + 1$$$ or $$$a_i = a_{i + 1} + 1$$$, then removing $$$a_i$$$ from array $$$a$$$.

Consider the largest value in $$$a$$$. If it is possible to delete it (meaning there is a value that is exactly one smaller than it to its left or right), we can delete it immediately. This is because keeping the largest value will not help to enable future operations as it can only help to delete elements that are $$$1$$$ greater than it, which is not possible for the largest value.

Now, all we have to do is to maintain all elements that can be deleted and choose the element with the largest value each time. Then, whenever we delete an element, we need to check whether the two adjacent elements become deletable and update accordingly. We can do this using a priority_queue and a linked list in $$$O(n\log n)$$$. Note that many other implementations exist, including several $$$O(n)$$$ solutions.

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

const int MAXN = 200005;

int n;
int a[MAXN];
int prv[MAXN],nxt[MAXN];
bool in[MAXN];

bool good(int i) {
    if (i < 1 || i > n) {
        return 0;
    }
    return a[prv[i]] == a[i] - 1 || a[nxt[i]] == a[i] - 1;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> n;
        priority_queue<pair<int, int>> pq;
        for (int i = 1; i <= n; i++) {
            prv[i] = i - 1;
            nxt[i] = i + 1;
            in[i] = 0;
            cin >> a[i];
        }
        a[n + 1] = a[0] = -2;
        for (int i = 1; i <= n; i++) {
            if (good(i)) {
                in[i] = 1;
                pq.push({a[i], i});
            }
        }
        while (!pq.empty()) {
            auto [_, i] = pq.top(); pq.pop();
            nxt[prv[i]] = nxt[i];
            prv[nxt[i]] = prv[i];
            if (!in[prv[i]] && good(prv[i])) {
                in[prv[i]]=1;
                pq.push({a[prv[i]], prv[i]});
            }
            if (!in[nxt[i]] && good(nxt[i])) {
                in[nxt[i]]=1;
                pq.push({a[nxt[i]], nxt[i]});
            }
        }
        int mn = n, bad = 0;
        for (int i = 1; i <= n; i++) {
            bad += !in[i];
            mn = min(a[i], mn);
        }
        if (bad == 1 && mn == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Try solving the problem if the sum of elements of array $$$a$$$ is equal to $$$s$$$. If we can do this in $$$O(n)$$$ time, we can iterate through all possible values of $$$p_1 \le s \le p_n$$$ and sum up the number of ways for each possible sum.

Consider starting with array $$$a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$$$ where there are $$$p_n$$$ occurences of $$$1$$$ and $$$p_n - s$$$ occurrences of $$$-1$$$. Then, try inserting $$$(-1, 1)$$$ into the array to fix the number of occurrences of prefix sum starting from the largest value ($$$p_n$$$) to the smallest value ($$$p_1$$$).

Let us try to solve the problem if the sum of elements of array $$$a$$$ is equal to $$$s$$$. Consider starting array $$$a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$$$ where there are $$$p_n$$$ occurrences of $$$1$$$ and $$$p_n - s$$$ occurrences of $$$-1$$$. Notice that when we insert $$$(-1, 1)$$$ into array $$$a$$$ between positions $$$i$$$ and $$$i + 1$$$ where the sum of $$$a$$$ from $$$1$$$ to $$$i$$$ is $$$s$$$, two new prefix sums $$$s - 1$$$ and $$$s$$$ will be formed while the remaining prefix sums remain the same. Let us try to fix the prefix sums starting from the largest prefix sum to the smallest prefix sum.

In the starting array $$$a$$$, we only have $$$1$$$ occurrence of prefix sum with value $$$p_n$$$. We can insert $$$(-1, 1)$$$ right after it $$$k$$$ times to increase the number of occurrences of prefix sum with value $$$p_n$$$ by $$$k$$$. In the process of doing so, the number of occurrences of prefix sum with value $$$p_n - 1$$$ also increased by $$$k$$$. Now, we want to fix the number of occurrences of prefix sum with value $$$p_n - 1$$$. If we already have $$$x$$$ occurrences but we require $$$y \gt x$$$ occurrences, we can choose to insert $$$y - 1$$$ pairs of $$$(-1, 1)$$$ right after any of the $$$x$$$ occurrences. We can calculate the number of ways using stars and bars to obtain the formula $$$y - 1\choose y - x$$$.

We continue using a similar idea to fix the number of occurrences of $$$p_n - 2, p_n - 3, \ldots, p_1$$$, each time considering the additional occurrences that were contributed from the previous layer. Each layer can be calculated in $$$O(1)$$$ time after precomputing binomial coefficients, so the entire calculation to count the number of array $$$a$$$ whose sum is $$$s$$$ and has prefix sum consistent to the input takes $$$O(n)$$$ time. Then, we can iterate through all possible $$$p_1 \le s \le p_n$$$ and sum up the answers to obtain a solution that works in $$$O(n^2)$$$ time.

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

typedef long long ll;
const int INF = 1000000005;
const int MAXN = 200005;
const int MOD = 998244353;

ll fact[MAXN * 2], ifact[MAXN * 2];
int t;
int n;
int f[MAXN * 2], d[MAXN * 2];

inline ll ncr(int n, int r) {
    if (r < 0 || n < r) {
        return 0;
    }
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
// count number of a_1 + a_2 + ... + a_n = x
inline ll starbar(int n, int x) {
    if (n == 0 && x == 0) {
        return 1;
    }
    return ncr(x + n - 1, x);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < MAXN * 2; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    ifact[0] = ifact[1] = 1;
    for (int i = 2; i < MAXN * 2; i++) {
        ifact[i] = MOD - MOD / i * ifact[MOD % i] % MOD;
    }
    for (int i = 2; i < MAXN * 2; i++) {
        ifact[i] = ifact[i - 1] * ifact[i] % MOD;
    }
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n * 2 + 5; i++) {
            f[i] = 0;
        }
        n++;
        for (int i = 1; i < n; i++) {
            int s; cin >> s;
            f[s + n]++;
        }
        f[n]++;
        int mn = INF, mx = -INF;
        for (int i = 0; i <= 2 * n; i++) {
            if (f[i]) {
                mn = min(mn, i);
                mx = max(mx, i);
            }
        }
        bool bad = 0;
        for (int i = mn; i <= mx; i++) {
            if (!f[i]) {
                bad = 1;
                break;
            }
        }
        if (bad || mn == mx) {
            cout << 0 << '\n';
            continue;
        }
        ll ans = 0;
        for (int x = mx; x >= mn; x--) {
            d[mx - 1] = f[mx] + (mx > n) - (mx == x);
            for (int i = mx - 2; i >= mn - 1; i--) {
                d[i] = f[i + 1] - d[i + 1] + (i >= x) + (i >= n);
            }
            if (d[mn - 1] != 0) {
                continue;
            }
            ll res = 1;
            for (int i = mx - 1; i >= mn; i--) {
                res = res * starbar(d[i], f[i] - d[i]) % MOD;
            }
            ans += res;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
        cout << ans << '\n';
    }
}

Solve the problem in $$$O(n)$$$ time.

Unfortunately, it seems like ARC146E is identical to this problem :(

When $$$c_i$$$ and $$$z$$$ equals $$$10^{18}$$$, it means that all the remaining water will always flow into the next water tower. Hence, the answer will be the sum of $$$a_i$$$ minus the amount of water remaining at tower $$$n$$$ after the process.

From hint 1, our new task now is to determine the amount of water remaining at tower $$$n$$$ after the process. Let $$$v_i = a_i - b_i$$$. The remaining amount of water remaining at tower $$$n$$$ is the maximum suffix sum of $$$v$$$, or more formally $$$\max\limits_{1\le k\le n}\ \sum\limits_{i = k}^n v_i$$$. We can use a segment tree where position $$$p$$$ of the segment tree stores $$$\sum\limits_{i = p}^n v_i$$$. The updates can be done using range prefix increment and the queries can be done using range maximum.

Code ReLU segment tree. A similar method can be used to solve the full problem if you combine even more ReLUs. However, it is not very elegant and is much more complicated than the intended solution below.

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

typedef long long ll;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

int n, q;
int a[MAXN], b[MAXN];
ll c[MAXN];
ll v[MAXN], sv[MAXN];

ll mx[MAXN * 4], lz[MAXN * 4];
void init(int u = 1, int lo = 1, int hi = n) {
    lz[u] = 0;
    if (lo == hi) {
        mx[u] = sv[lo];
    } else {
        int mid = lo + hi >> 1;
        init(u << 1, lo, mid);
        init(u << 1 ^ 1, mid + 1, hi);
        mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
    }
}
void propo(int u) {
    if (lz[u] == 0) {
        return;
    }
    lz[u << 1] += lz[u];
    lz[u << 1 ^ 1] += lz[u];
    mx[u << 1] += lz[u];
    mx[u << 1 ^ 1] += lz[u];
    lz[u] = 0;
}
void incre(int s, int e, ll x, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        mx[u] += x;
        lz[u] += x;
        return;
    }
    propo(u);
    int mid = lo + hi >> 1;
    if (s <= mid) {
        incre(s, e, x, u << 1, lo, mid);
    }
    if (e > mid) {
        incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    }
    mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> c[i];
    }
    ll sma = 0;
    for (int i = n; i >= 1; i--) {
        v[i] = a[i] - b[i];
        sv[i] = v[i] + sv[i + 1];
        sma += a[i];
    }
    init();
    while (q--) {
        int p, x, y; ll z; cin >> p >> x >> y >> z;
        sma -= a[p];
        incre(1, p, -v[p]);
        a[p] = x;
        b[p] = y;
        v[p] = a[p] - b[p];
        sma += a[p];
        incre(1, p, v[p]);
        cout << sma - max(0ll, mx[1]) << '\n';
    }
}

Try modelling this problem into a maximum flow problem.

Try using minimum cut to find the maximum flow.

Speed up finding the minimum cut using a segment tree.

Consider a flow graph with $$$n + 2$$$ vertices. Let the source vertex be $$$s = n + 1$$$ and the sink vertex be $$$t = n + 2$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$, add edge $$$s\rightarrow i$$$ with capacity $$$a_i$$$ and another edge $$$i\rightarrow t$$$ with capacity $$$b_i$$$. Then for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, add edge $$$i\rightarrow i + 1$$$ with capacity $$$c_i$$$. The maximum flow from $$$s$$$ to $$$t$$$ will be the answer to the problem.

Let us try to find the minimum cut of the above graph instead.

Claim: The minimum cut will contain exactly one of $$$s\rightarrow i$$$ or $$$i\rightarrow t$$$ for all $$$1\le i\le n$$$.

Proof: If the minimum cut does not contain both $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$, $$$s$$$ can reach $$$t$$$ through vertex $$$i$$$ and hence it is not a minimum cut. Now, we will prove why the minimum cut cannot contain both $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$. Suppose there exists a minimum cut where there exists a vertex $$$1\le i\le n$$$ where $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$ are both in the minimum cut. We will consider two cases:

• Case 1: $$$s$$$ can reach $$$i$$$ (through some sequence of vertices $$$s\rightarrow j\rightarrow j+1\rightarrow \ldots \rightarrow i$$$ where $$$j \lt i$$$). If our minimum cut only contains $$$i\rightarrow t$$$ without $$$s\rightarrow i$$$, nothing changes as $$$s$$$ was already able to reach $$$i$$$ when $$$s\rightarrow i$$$ was removed. Hence, $$$s$$$ will still be unable to reach $$$t$$$ and we found a minimum cut that has equal or smaller cost.
• Case 2: $$$s$$$ cannot reach $$$i$$$. If our minimum cut only contains $$$s\rightarrow i$$$ without $$$i\rightarrow t$$$, nothing changes as $$$s$$$ is still unable to reach $$$i$$$, so we cannot make use of the edge $$$i\rightarrow t$$$ to reach $$$t$$$ from $$$s$$$. Hence, $$$s$$$ will still be unable to reach $$$t$$$ and we found a minimum cut that has equal or smaller cost.

Now, all we have to do is select for each $$$1\le i\le n$$$, whether to cut the edge $$$s\rightarrow i$$$ or the edge $$$i\rightarrow t$$$. Let us use a string $$$x$$$ consisting of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$ to represent this. $$$x_i = \texttt{A}$$$ means we decide to cut the edge $$$s\rightarrow i$$$ for a cost of $$$a_i$$$ and $$$x_i = \texttt{B}$$$ means we decide to cut the edge from $$$i\rightarrow t$$$ for a cost of $$$b_i$$$. Notice that whenever we have $$$x_i = \texttt{B}$$$ and $$$x_{i + 1} = \texttt{A}$$$, $$$s$$$ can reach $$$t$$$ through $$$s\rightarrow i\rightarrow i + 1\rightarrow t$$$. To prevent this, we have to cut the edge $$$i\rightarrow i + 1$$$ for a cost of $$$c_i$$$.

To handle updates, we can use a segment tree. Each node of the segment tree stores the minimum possible cost for each of the four combinations of the two endpoints being $$$\texttt{A}$$$ or $$$\texttt{B}$$$. When merging the segment tree nodes, add a cost of $$$c$$$ when the right endpoint of the left node is $$$\texttt{B}$$$ and the left endpoint of the right node is $$$\texttt{A}$$$. The final time complexity is $$$O(n\log n)$$$ as only a segment tree is used.

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

typedef long long ll;
const ll LINF = 1000000000000000005ll;
const int MAXN = 500005;

int n, q;
int a[MAXN], b[MAXN];
ll c[MAXN];

ll st[MAXN * 4][2][2];
void merge(int u, int lo, int hi) {
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    for (int l = 0; l < 2; l++) {
        for (int r = 0; r < 2; r++) {
            st[u][l][r] = min({st[lc][l][0] + st[rc][0][r],
                    st[lc][l][1] + st[rc][1][r],
                    st[lc][l][0] + st[rc][1][r],
                    st[lc][l][1] + st[rc][0][r] + c[mid]});
        }
    }
}
void init(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[u][0][0] = a[lo];
        st[u][1][1] = b[lo];
        st[u][1][0] = st[u][0][1] = LINF;
        return;
    }
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    init(lc, lo, mid);
    init(rc, mid + 1, hi);
    merge(u, lo, hi);
}
void upd(int p, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[u][0][0] = a[lo];
        st[u][1][1] = b[lo];
        st[u][1][0] = st[u][0][1] = LINF;
        return;
    }
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    if (p <= mid) {
        upd(p, lc, lo, mid);
    } else {
        upd(p, rc, mid + 1, hi);
    }
    merge(u, lo, hi);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> c[i];
    }
    init();
    while (q--) {
        int p, x, y; ll z; cin >> p >> x >> y >> z;
        a[p] = x; b[p] = y; c[p] = z;
        upd(p);
        cout << min({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]}) << '\n';
    }
}

Think about how you would construct matrix $$$s$$$ if you were given the tree.

If $$$s_{i, i} = \mathtt{0}$$$, what should the value of $$$s_{j, i}$$$ be for all $$$1\le j\le n$$$?

For some $$$i$$$ where $$$s_{i, i} = \mathtt{1}$$$, let $$$Z$$$ be a set containing all the vertices $$$j$$$ where $$$s_{j, i} = \mathtt{0}$$$. More formally, $$$Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, i} = \mathtt{0}\}$$$. Does $$$Z$$$ have any special properties?

Using hint 3, can we break down the problem into smaller sub-problems?

Try solving the problem if the values in each column are a constant. In other words, $$$s_{i, j} = s_{j, j}$$$ for all $$$1\le i\le n$$$ and $$$1\le j\le n$$$.

Let us consider how we can code the checker for this problem. In other words, if we are given a tree, how can we construct matrix $$$s$$$? We can solve this using dynamic programming. $$$s_{i, j} = \mathtt{1}$$$ if and only if at least one child $$$c$$$ of vertex $$$j$$$ (when the tree is rooted at vertex $$$i$$$) has $$$s_{i, c} = \mathtt{0}$$$. This is because the player can move the coin from vertex $$$j$$$ to vertex $$$c$$$ which will cause the opponent to be in a losing state.

For convenience, we will call a vertex $$$i$$$ special if there exists some $$$1\le j\le n$$$ where $$$s_{j, i} \neq s_{i, i}$$$. Suppose there exist some $$$i$$$ where $$$s_{i, i} = \mathtt{0}$$$. This means that moving the coin to any of the neighbours of $$$i$$$ results in a winning state for the opponent. If the tree was rooted at some other vertex $$$j\neq i$$$, it will still be a losing state as it reduces the options that the player can move the coin to, so $$$s_{j, i}$$$ should be $$$\mathtt{0}$$$ for all $$$1\le j\le n$$$. This means that special vertices must have $$$s_{i, i} = \mathtt{1}$$$

Now, let us take a look at special vertices. Let $$$x$$$ be a special vertex, meaning $$$s_{x, x} = \mathtt{1}$$$ and there exist some $$$j$$$ where $$$s_{j, x} = \mathtt{0}$$$. Let $$$Z$$$ be a set containing all the vertices $$$j$$$ where $$$s_{j, x} = \mathtt{0}$$$. More formally, $$$Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, x} = \mathtt{0}\}$$$. $$$Z$$$ cannot be empty due to the property of special vertices. Notice that whenever we choose to root at some vertex $$$j\neq x$$$, the number of children of $$$x$$$ decreases by exactly $$$1$$$. This is because the neighbour that lies on the path from vertex $$$x$$$ to vertex $$$j$$$ becomes the parent of $$$x$$$ instead of the child of $$$x$$$. If rooting the tree at vertex $$$x$$$ is a winning state but rooting the tree at some other vertex $$$j$$$ results in a losing state instead, it means that the only winning move is to move the coin from vertex $$$x$$$ to the neighbour that is on the path from vertex $$$x$$$ to $$$j$$$.

Let $$$y$$$ denote the only neighbour of vertex $$$x$$$ where we can move the coin from vertex $$$x$$$ to vertex $$$y$$$ and win. In other words, $$$y$$$ is the neighbour of vertex $$$x$$$ where $$$y$$$ lies on the path of the vertices in set $$$Z$$$ and $$$x$$$. This means that $$$Z$$$ is the set of vertices that are in the subtree of $$$y$$$ rooted at vertex $$$x$$$.

Now, let us try to find vertex $$$y$$$. Notice that $$$s_{y, y} = \mathtt{1}$$$. This is because $$$s_{y, x} = \mathtt{0}$$$, so the coin can be moved from vertex $$$y$$$ to vertex $$$x$$$ to result in a losing state for the opponent. Furthermore, $$$s_{j, y} = \mathtt{0}$$$ if and only if $$$j$$$ is not in $$$Z$$$, otherwise $$$s_{j, y} = \mathtt{1}$$$. This is because $$$s_{x, y} = \mathtt{0}$$$ since moving the coin from vertex $$$x$$$ to vertex $$$y$$$ is a winning move for the first player. For all other vertex $$$u\in Z$$$ that is not $$$y$$$, this property will not hold as even if $$$s_{u, u} = \mathtt{1}$$$ and $$$s_{x, u} = \mathtt{0}$$$, $$$s_{y, u}$$$ will be equal to $$$\mathtt{0}$$$ as well as the tree being rooted at $$$x$$$ has the same effect as if it was rooted at $$$y$$$. Since $$$y \in Z$$$, $$$s_{y, u} = \mathtt{0}$$$ does not satisfy $$$s_{j, u} = \mathtt{1}$$$ for all $$$j$$$ in $$$Z$$$.

Since $$$y$$$ is a neighbour of vertex $$$x$$$, we know that there is an edge between vertex $$$y$$$ and $$$x$$$. Furthermore, we know that if the edge between vertex $$$y$$$ and $$$x$$$ is removed, the set of vertices $$$Z$$$ forms a single connected component containing $$$y$$$, while the set of vertices not in $$$Z$$$ forms another connected component containing $$$x$$$. This means that we can recursively solve the problem for the two connected components to check whether the values in the matrix $$$s$$$ are valid within their components.

After recursively solving for each connected component, we are only left with non-special vertices ($$$s_{j, i} = s_{i, i}$$$ for all $$$1\le j\le n$$$) and some special vertices that already have an edge that connects to outside the component. Non-special vertices with $$$s_{i, i} = \mathtt{1}$$$ has to be connected to at least $$$2$$$ non-special vertices with $$$s_{i, i} = \mathtt{0}$$$. The most optimal way to do this is to form a line 0 — 1 — 0 — 1 — 0 as it requires the least amount of $$$s_{i, i} = \mathtt{0}$$$. If there is not enough $$$s_{i, i} = \mathtt{0}$$$ to form the line, a solution does not exist. Otherwise, connect the left-over $$$s_{i, i} = \mathtt{0}$$$ to any of $$$s_{i, i} = \mathtt{1}$$$. On the other hand, special vertices can either be connected to nothing, connected to other special vertices, or connected to non-special vertices with $$$s_{i, i} = \mathtt{1}$$$.

For the final step, we need to check whether $$$s_{i, j}$$$ is consistent when $$$i$$$ and $$$j$$$ are in different components (i.e. ($$$i\in Z$$$ and $$$j\notin Z$$$) or ($$$i\notin Z$$$ and $$$j\in Z$$$)). Notice that $$$s_{i, j} = s_{x, j}$$$ for all $$$i\in Z$$$ and $$$j\notin Z$$$ and $$$j\neq x$$$, and $$$s_{i, j} = s_{y, j}$$$ for all $$$i\notin Z$$$ and $$$j\in Z$$$ and $$$j\neq y$$$. From the steps above, we managed to account for every value in the matrix, hence if matrix $$$s$$$ is consistent through all the steps, the constructed tree would be valid as well.

We can make use of xor hash to find vertex $$$x$$$ together with its corresponding vertex $$$y$$$. With xor hash, the time complexity is $$$O(n^2)$$$. Well-optimised bitset code with time complexity of $$$O(\frac{n^3}{w})$$$ can pass as well.

#include <bits/stdc++.h> 
using namespace std;
 
const int MAXN = 5005;

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
 
int n;
unsigned long long r[MAXN], hsh[MAXN], totr;
string s[MAXN];
vector<pair<int, int>> ans;
 
bool done[MAXN];
bool solve(vector<int> grp) {
    int pr = -1, pl = -1;
    vector<int> lft, rht;
    for (int i : grp) {
        if (s[i][i] == '0' || done[i] || hsh[i] == totr) {
            continue;
        }
        rht.clear();
        for (int j : grp) {
            if (s[j][i] == '0') {
                lft.push_back(j);
            } else {
                rht.push_back(j);
            }
        }
        if (!lft.empty()) {
            pr = i;
            break;
        }
    }
    if (pr == -1) {
        vector<int> dv, zero, one;
        for (int i : grp) {
            if (done[i]) {
                dv.push_back(i);
            } else if (s[i][i] == '0') {
                zero.push_back(i);
            } else {
                one.push_back(i);
            }
        }
        for (int i = 1; i < dv.size(); i++) {
            ans.push_back({dv[i - 1], dv[i]});
        }
        if (one.empty() && zero.empty()) {
            return 1;
        }
        if (one.size() >= zero.size()) {
            return 0;
        }
        if (one.empty()) {
            if (zero.size() >= 2 || !dv.empty()) {
                return 0;
            }
            return 1;
        }
        for (int i = 0; i < one.size(); i++) {
            ans.push_back({zero[i], one[i]});
            ans.push_back({one[i], zero[i + 1]});
        }
        for (int i = one.size() + 1; i < zero.size(); i++) {
            ans.push_back({one[0], zero[i]});
        }
        if (!dv.empty()) {
            ans.push_back({one[0], dv[0]});
        }
        return 1;
    }
    for (int i : lft) {
        if (s[i][i] == '0' || done[i] || ((hsh[i] ^ hsh[pr]) != totr)) {
            continue;
        }
        vector<int> trht;
        for (int j : grp) {
            if (s[j][i] == '0') {
                trht.push_back(j);
            }
        }
        if (trht == rht) {
            pl = i;
            break;
        }
    }
    if (pl == -1) {
        return 0;
    }
    for (int i : lft) {
        for (int j : rht) {
            if (j == pr) {
                continue;
            }
            if (s[i][j] != s[pr][j]) {
                return 0;
            }
        }
    }
    for (int i : rht) {
        for (int j : lft) {
            if (j == pl) {
                continue;
            }
            if (s[i][j] != s[pl][j]) {
                return 0;
            }
        }
    }
    ans.push_back({pl, pr});
    done[pl] = done[pr] = 1;
    return solve(lft) && solve(rht);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        r[i] = rnd();
        totr ^= r[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1') {
                hsh[j] ^= r[i];
            }
        }
    }
    bool pos = 1;
    for (int i = 0; i < n; i++) {
        if (s[i][i] == '1') {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if (s[j][i] == '1') {
                pos = 0;
                break;
            }
        }
    }
    if (!pos) {
        cout << "NO\n";
        return 0;
    }
    vector<int> v(n, 0);
    iota(v.begin(), v.end(), 0);
    if (!solve(v)) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (auto [u, v] : ans) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

The original problem allowed $$$5n$$$ type 1 queries and $$$n$$$ type 2 queries and was used as the last problem of a Div. 2 round. When we opened the round for testing, dario2994 solved the problem using $$$2n$$$ type 1 queries, and a few days later, he managed to improve his solution to use only $$$n$$$ type 1 queries. This was what made us decide to change this round into a Div. 1 round instead of a Div. 2 round.

Try rooting the tree at an edge.

Use $$$n - 2$$$ of query $$$2$$$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge.

We start with only the root edge, then add edges of depth $$$0$$$, followed by depth $$$1, 2, \ldots$$$

If we want to add a new edge with depth $$$i$$$, we need to attach it to one of the edges with depth $$$i - 1$$$. We can let the weight of the edge we want to attach be $$$10^9$$$ to force the diameter to pass through it, then let the edges of depth $$$i - 1$$$ have weights be different multiples of $$$n$$$. This way, we can determine which edges of depth $$$i - 1$$$ are used in the diameter (unless the two largest edges are used).

Make use of isomorphism to handle the case in hint 4 where the largest two edges are used.

If isomorphism cannot be used, find a leaf edge of a lower depth than the query edge and force the diameter to pass through the leaf edge and the query edge. Then, only 1 edge of depth $$$i - 1$$$ will be used and the edge weights for edges of depth $$$i - 1$$$ can follow a similar structure as hint 4.

We will root the tree at edge $$$1$$$. Then, use $$$n - 2$$$ of query $$$2$$$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge. Our objective is to add the edges in increasing order of depth, so when we are inserting an edge of depth $$$i$$$, all edges of depth $$$i - 1$$$ are already inserted and we just have to figure out which edge of depth $$$i - 1$$$ we have to attach the edge of depth $$$i$$$ to.

For convenience, the edge weights used in query $$$1$$$ will be $$$1$$$ by default unless otherwise stated. Let $$$c_i$$$ store the list of edges with depth $$$i$$$. Suppose we want to insert edge $$$u$$$ into the tree and the depth of edge $$$u$$$ is $$$d$$$. We let the weight of the edge $$$u$$$ be $$$10 ^ 9$$$ and the weight of edges in $$$c_{d - 1}$$$ be $$$n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, (|c_{d - 1}| - 1)n$$$. The diameter will pass through edge $$$u$$$, the parent edge of $$$u$$$, as well as one edge of weight $$$(|c_{d - 1}| - 1)n$$$. If we calculate $$$\left\lfloor\frac{\text{diameter} - 10^9}{n}\right\rfloor - (|c_{d - 1}| - 1)$$$, we will be able to tell the index of the parent edge of $$$u$$$.

However, there is one exception. When the parent edge of $$$u$$$ is one of the last 2 edges of $$$c_{d - 1}$$$, we are unable to differentiate between the two of them as they have the same weight. This is not a problem if the last 2 edges are isomorphic to each other, as attaching $$$u$$$ to either parent results in the same tree. For now, we will assume that the last 2 edges of $$$c_{d - 1}$$$ are isomorphic to each other.

However, after attaching edge $$$u$$$ to one last 2 edges in $$$c_{d - 1}$$$, they are no longer isomorphic. Hence, we need to use a different method to insert the remaining edges of depth $$$d$$$. Let the new edge that we want to insert be $$$v$$$. Let the weight of edges $$$u$$$ and $$$v$$$ be $$$10^9$$$ and the weights of edges in $$$c_{d - 1}$$$ be the same as before. Now, we can use $$$\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$$$ to determine whether edge $$$v$$$ share the same parent as $$$u$$$, and if it does not share the same parent, it can still determine the index of the parent edge of $$$v$$$. With the additional information of whether edge $$$v$$$ shares the same parent as edge $$$u$$$, we will be able to differentiate the last 2 edges of $$$c_{d - 1}$$$ from each other.

Now, we just need to handle the issue where the last 2 edges of $$$c_{d - 1}$$$ are not isomorphic. When we only have the root edge at the start, the left and right ends of the edge are isomorphic (note that for the root edge, we consider it as 2 separate edges, one with the left endpoint and one with the right endpoint). We try to maintain the isomorphism as we add edges of increasing depth. Suppose the last two edges of $$$c_{d - 1}$$$ are isomorphic. Let the two edges be $$$a$$$ and $$$b$$$. Then, we insert edges of depth $$$d$$$ using the above method. Let the child edges attached to $$$a$$$ and $$$b$$$ be represented by sets $$$S_a$$$ and $$$S_b$$$ respectively. If either $$$S_a$$$ or $$$S_b$$$ has sizes at least $$$2$$$, the two edges in the same set will be isomorphic, so we can let those 2 edges be the last 2 edges of $$$c_d$$$. Now, the sizes of $$$S_a$$$ and $$$S_b$$$ are both strictly smaller than $$$2$$$. If the sizes of both sets are exactly $$$1$$$, the two edges from each set will be isomorphic as well as $$$a$$$ and $$$b$$$ are isomorphic. Now, the only case left is if at least one of the sets is empty.

Without loss of generality, assume that $$$S_a$$$ is empty. Since it is no longer possible to maintain two isomorphic edges, we now change our objective to find a leaf (it will be clear why in the following paragraphs). If $$$S_b$$$ is empty as well, both $$$a$$$ and $$$b$$$ are leaves so we can choose any one of them. If $$$S_b$$$ is not empty, then $$$a$$$ and $$$b$$$ are no longer isomorphic due to their children. This means that we cannot simply use $$$b$$$ as the leaf $$$S_a$$$ might be children of $$$b$$$ instead of $$$a$$$ as we did not differentiate $$$a$$$ and $$$b$$$ in the previous paragraphs. To determine whether $$$S_a$$$ belongs to $$$a$$$ or $$$b$$$, we can make use of one type 2 query to find the distance between one of the edges in $$$S_a$$$ and $$$a$$$. If the distance is $$$0$$$, it means that $$$S_a$$$ belongs to $$$a$$$. Otherwise, the distance will be $$$1$$$ and $$$S_a$$$ belongs to $$$b$$$.

Now that we found a leaf, we can use the following method to insert an edge $$$u$$$ of depth $$$d$$$. We let the weight of the edge $$$u$$$ and the leaf edge be $$$10 ^ 9$$$ and the weight of edges in $$$c_{d - 1}$$$ be $$$n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, |c_{d - 1}|n$$$. The diameter will pass through edge $$$u$$$, the leaf edge, and only one edge of depth $$$d - 1$$$ which is the parent edge of $$$u$$$. Hence, after finding a leaf edge, we can uniquely determine the parent edge from $$$\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$$$.

We used $$$n - 2$$$ type 1 queries and $$$n - 1$$$ type 2 queries in total. This is because we used a single type 1 query for each non-root edge. We used $$$n - 2$$$ type 2 queries at the start, and we only used $$$1$$$ additional type 2 query when we were no longer able to maintain two isomorphic edges and changed our methodology to use a leaf edge instead.

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

typedef long long ll;
const int INF = 1000000000;
const int MAXN = 1000;

int n;
int lvl[MAXN + 5];
int pe[MAXN + 5];
vector<int> ch[MAXN + 5];

ll query(vector<int> a) {
    cout << "? 1";
    for (int i = 1; i < n; i++) {
        cout << ' ' << a[i];
    }
    cout << endl;
    ll res; cin >> res;
    return res;
}
int query(int a, int b) {
    cout << "? 2 " << a << ' ' << b << endl;
    int res; cin >> res;
    return res;
}

int main() {
    cin >> n;
    for (int i = 2; i < n; i++) {
        lvl[i] = query(1, i);
    }
    int ptr = 3;
    vector<int> base = {1, 2};
    pe[1] = pe[2] = 1;
    bool iso = 1;
    int piv = -1;
    for (int l = 0; l < n; l++) {
        vector<int> a(n, 1);
        int m = base.size();
        for (int i = 0; i < m; i++) {
            a[pe[base[i]]] = min(i + 1, m - iso) * MAXN;
        }
        if (!iso) {
            a[pe[piv]] = INF;
        }
        bool ciso = 0;
        for (int u = 2; u < n; u++) {
            if (lvl[u] != l) {
                continue;
            }
            a[u] = INF;
            ll res = query(a) - INF;
            a[u] = 1;
            if (!iso || ciso) {
                res -= INF;
            }
            int id = res / MAXN;
            if (iso && l) {
                id -= m - 1;
            }
            int v = ptr++;
            pe[v] = u;
            if (ciso) {
                if ((l == 0 && id == 0) || id == -(m - 1)) {
                    ch[base[m - 2]].push_back(v);
                } else if (id == m - 1) {
                    ch[base[m - 1]].push_back(v);
                } else {
                    ch[base[id - 1]].push_back(v);
                }
            } else if (iso && id == m - 1) {
                ch[base[m - 2]].push_back(v);
                ciso = 1;
                a[u] = INF;
            } else {
                ch[base[id - 1]].push_back(v);
            }
        }
        if (m >= 2 && ch[base[m - 2]].size() > ch[base[m - 1]].size()) {
            swap(base[m - 2], base[m - 1]);
        }
        vector<int> nbase;
        for (int i = 0; i < m; i++) {
            for (int j : ch[base[i]]) {
                nbase.push_back(j);
            }
        }
        if (!iso || ch[base[m - 1]].size() >= 2 || ch[base[m - 2]].size() == 1) {
            base = nbase;
            continue;
        }
        if (ch[base[m - 1]].empty()) {
            piv = base[m - 1];
        } else {
            ll res = query(pe[ch[base[m - 1]][0]], pe[base[m - 1]]);
            if (res) {
                swap(base[m - 2], base[m - 1]);
                swap(ch[base[m - 2]], ch[base[m - 1]]);
            }
            piv = base[m - 2];
        }
        iso = 0;
        base = nbase;
    }
    cout << '!' << endl;
    cout << 1 << ' ' << 2 << endl;
    for (int u = 1; u <= n; u++) {
        for (int v : ch[u]) {
            cout << u << ' ' << v << endl;
        }
    }
}