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.

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.

Classic O(N) Stack Construction  
We maintain a stack of nodes whose a‐values form a strictly increasing sequence from bottom to top. We iterate through the nodes in ascending k‐order:

Let the current node index be i, with auxiliary key A = a[i].  
Initialize last = −1.  
While the stack is nonempty and a[stack.top] > A:  
  – Pop the top, call it topIdx.  
  – Set last = topIdx.  
End-while  

At this point all popped nodes have A less than their a‐values, so node i will become their parent. In fact the largest of these popped nodes (the last popped) becomes the left child of i:  
  If last ≠ −1:  
    parent[last] = i;  
    left[i] = last;  

Now, if the stack is still nonempty, its current top has a smaller auxiliary key than A, so that node becomes the parent of i, with i as its right child:  
  If stack not empty:  
    parent[i] = stack.top();  
    right[stack.top()] = i;  

Finally, push i onto the stack.

After processing all nodes, the bottom element of the stack is the root (its parent remains −1). We then output parent/left/right offsets (converted from −1 to 0). This runs in O(N) time and O(N) memory.

3. Original C++ Solution with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// For convenience: print/read pairs and vectors
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;  // (k, a)

// Read input: N and pairs
void read() {
    cin >> n;
    a.resize(n);
    cin >> a;  // using our operator>>
}

void solve() {
    // Create an array of indices [0..n-1], sort them by main key k
    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; });

    // parent, left child, right child; initialize to -1 (none)
    vector<int> parent(n, -1), leftC(n, -1), rightC(n, -1);

    vector<int> st;  // will store a stack of indices, increasing in a[]

    // Process each node in ascending k
    for (int idx : order) {
        int last = -1;
        // Pop from stack until top.a <= current.a
        while (!st.empty() && a[st.back()].second > a[idx].second) {
            last = st.back();
            st.pop_back();
        }
        // The last popped becomes left child of current
        if (last != -1) {
            parent[last] = idx;
            leftC[idx] = last;
        }
        // If stack non-empty now, top becomes parent of current
        if (!st.empty()) {
            parent[idx] = st.back();
            rightC[st.back()] = idx;
        }
        // Push current onto stack
        st.push_back(idx);
    }

    // Output result
    cout << "YES\n";
    // Convert -1 to 0 and +1 for 1-based indexing
    for (int i = 0; i < n; i++) {
        int p = (parent[i] == -1 ? 0 : parent[i]+1);
        int l = (leftC[i] == -1   ? 0 : leftC[i]+1);
        int r = (rightC[i] == -1  ? 0 : rightC[i]+1);
        cout << p << ' ' << l << ' ' << r << "\n";
    }
}

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

    read();
    solve();
    return 0;
}
```

4. Python Solution with Comments  
```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 in O(N): for each new node remove from the stack all nodes with larger a, attaching them as its left subtree; if the stack remains nonempty, attach the new node as the right child of the stack’s top. The result is the unique Cartesian tree.