#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
 
const int maxn=50005;
int stk[maxn],pre[maxn],rson[maxn],lson[maxn];
 
struct Node {
    int val;
    int pri;
    int id;
} a[maxn];
 
int up(Node x,Node y) {
    return x.pri<y.pri;
}
 
stack<Node> ST; //Monotone stack
void buildCartesianTree(int n) {
    for(int i=1; i<=n; i++) {
        Node u=a[i];
        Node t;
        bool flag=0;
        while(!ST.empty() && u.val<ST.top().val) {
            t=ST.top();
            ST.pop();
            flag=1;
        }
 
        if(flag) {
            pre[t.id]=u.id;
            lson[u.id]=t.id;
        }
 
        if(!ST.empty()) {
            pre[u.id]=ST.top().id;
            rson[ST.top().id]=u.id;
        } else pre[u.id]=0;
 
        ST.push(u);
    }
}
 
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i].pri>>a[i].val;
        a[i].id=i;
    }
 
    sort(a+1,a+1+n,up);
    buildCartesianTree(n);
 
    cout<<"YES"<<endl;
    for(int i=1; i<=n; i++) {
        cout<<pre[i]<<" "<<lson[i]<<" "<<rson[i]<<endl;
    }
    return 0;
}

1. 数据结构定义：

   • stk[maxn] 数组、pre[maxn] 数组、rson[maxn] 数组和 lson[maxn] 数组分别用于存储单调栈、节点的父节点、节点的右子节点和节点的左子节点。
   • Node 结构体包含节点的主键 val、辅助键 pri 和节点编号 id。

2. 比较函数 up：

   • 函数 up 用于比较两个节点的辅助键，按照辅助键从小到大的顺序进行排序。

3. 构建笛卡尔树函数 buildCartesianTree：

   • 遍历输入的节点，对于每个节点 u：
     • 当单调栈不为空且当前节点 u 的主键小于栈顶节点的主键时，弹出栈顶节点 t，并设置 t 的父节点为 u，u 的左子节点为 t，标记 flag 为 1。
     • 如果单调栈不为空，设置 u 的父节点为栈顶节点，栈顶节点的右子节点为 u；否则设置 u 的父节点为 0。
     • 将节点 u 压入单调栈。

4. 主函数 main：

   • 读取节点数量 n。
   • 读取每个节点的主键和辅助键，并为每个节点分配编号。
   • 使用 sort 函数按照辅助键对节点进行排序。
   • 调用 buildCartesianTree 函数构建笛卡尔树。
   • 输出 YES，并遍历每个节点，输出其父亲节点、左子节点和右子节点。

代码通过单调栈的方式，根据笛卡尔树的性质，利用辅助键的堆性质和主键的二叉搜索树性质，构建出笛卡尔树，并输出树的相关信息。