1. Abridged Problem Statement
Given N pairs (k_i, a_i) with all k's and a's distinct, build a Cartesian tree:
- It must be a binary search tree in k (i.e. in-order traversal visits nodes in increasing k),
- It must satisfy the min–heap property in a (every parent's a is less than its children's a).
If possible, print YES and for each node i (1…N in input order) output three integers: its parent index, left child index and right child index (use 0 if absent). Otherwise print NO.

2. Detailed Editorial

Definition and Uniqueness
A Cartesian tree on a sequence of pairs (k,a) is a binary tree that is simultaneously:
  a) a binary search tree with respect to k, and
  b) a min-heap with respect to a.
When all k's are distinct and all a's are distinct, the Cartesian tree is unique, so the answer is always YES.

Reduction to Sequence and In-Order
If you sort the nodes by k ascending, then any BST in k must have its in-order traversal exactly this sorted order. Thus we only need to arrange these N nodes in a binary tree so that in-order is the sorted-by-k sequence and so that the a-values satisfy the heap condition.

Monotonic Stack on the Right Spine
We process nodes in ascending k order while keeping a stack that holds the current right spine of the partially built tree, with auxiliary keys increasing from bottom to top. For each new node i:

  – Initialize last = -1.
  – While the stack is nonempty and a[top] > a[i], pop the top via a "collapse" step. Collapse removes the top of the stack, and if there is a previously popped node (last), it makes that node the right child of the element we just popped (because, among the popped chain, smaller-key nodes hang to the right of larger-key ones). It returns the popped index as the new `last`.
  – After the while-loop, the final value of `last` is the root of the just-popped subtree; that whole subtree becomes the left child of node i (par[last] = i, l[i] = last).
  – Push i onto the stack.

After all nodes are processed, the stack still contains the final right spine; we flush it with the same collapse routine to link the remaining right-child edges. The bottom element ends up as the root (its parent stays -1).

We output parent/left/right offsets (converted from -1 to 0, shifted to 1-based). This runs in O(N log N) for the sort plus O(N) for the stack work, with O(N) memory.

3. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<pair<int, int>> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // Build a Cartesian tree (BST on the main key, min-heap on the auxiliary
    // key) with a monotone stack. We process nodes in increasing main-key
    // order; the stack holds the right spine of the tree built so far, with
    // auxiliary keys increasing from bottom to top. For each new node we pop
    // every spine element whose auxiliary key is larger; the last popped one
    // becomes the new node's left child, and the new node becomes the right
    // child of whatever remains on top. par/l/r store parent, left child and
    // right child (0 meaning none).

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return a[i].first < a[j].first;
    });

    vector<int> par(n, -1);
    vector<int> l(n, -1), r(n, -1);
    vector<int> st;

    function<int(int)> collapse = [&](int last) {
        int prev_top = st.back();
        st.pop_back();

        if(last != -1) {
            par[last] = prev_top;
            r[prev_top] = last;
        }

        return prev_top;
    };

    for(int i: order) {
        int last = -1;
        while(!st.empty() && a[st.back()].second > a[i].second) {
            last = collapse(last);
        }

        if(last != -1) {
            par[last] = i;
            l[i] = last;
        }

        st.push_back(i);
    }

    cout << "YES\n";

    int last = -1;
    while(!st.empty()) {
        last = collapse(last);
    }

    for(int i = 0; i < n; i++) {
        cout << par[i] + 1 << ' ' << l[i] + 1 << ' ' << r[i] + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution
```python
import sys
sys.setrecursionlimit(10**7)

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    # Read pairs (k, a) along with original index
    nodes = []
    idx = 1
    for i in range(n):
        k = int(data[idx]); a = int(data[idx+1])
        idx += 2
        nodes.append((k, a, i))
    # Sort by k to enforce BST in-order
    nodes.sort(key=lambda x: x[0])

    parent = [-1]*n
    leftC  = [-1]*n
    rightC = [-1]*n
    stack = []

    # Build Cartesian tree in O(n)
    for k, a_val, orig in nodes:
        last = -1
        # Pop those with larger a
        while stack and stack[-1][1] > a_val:
            last = stack.pop()[2]  # record original index
        # last becomes left child of current
        if last != -1:
            parent[last] = orig
            leftC[orig] = last
        # if stack not empty, top becomes parent of current
        if stack:
            parent[orig] = stack[-1][2]
            rightC[stack[-1][2]] = orig
        # push current
        stack.append((k, a_val, orig))

    # Print YES and the triples with 1-based indices / 0 for none
    out = ["YES"]
    for i in range(n):
        p = 0 if parent[i] < 0 else parent[i] + 1
        l = 0 if leftC[i]  < 0 else leftC[i]  + 1
        r = 0 if rightC[i] < 0 else rightC[i] + 1
        out.append(f"{p} {l} {r}")
    print("\n".join(out))

if __name__ == "__main__":
    main()
```

5. Compressed Editorial
Sort nodes by k to fix in-order. Build a min-heap over a via a monotonic stack holding the right spine in O(N): for each new node pop all spine nodes with larger a (linking each smaller-key popped node as the right child of the one above it), attach the last popped chain as the new node's left subtree, then push it. Flush the remaining spine at the end. The result is the unique Cartesian tree.
