Sgu/155

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int k,a;
    int index;
    bool operator <(const node &b) const
    {
        return k<b.k;
    }
}num[60000];
int pa[60000];
int lson[60000];
int rson[60000];
int d[51000][20];
int rec[51000][20];
int rmq(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    if(d[l][k]<d[r-(1<<k)+1][k])
    return rec[l][k];
    else return rec[r-(1<<k)+1][k];
}
int n;
int build(int l,int r)
{
    if(l>r) return 0;
    int minst=rmq(l,r);
    int id=num[minst].index;
    lson[id]=build(l,minst-1);
    rson[id]=build(minst+1,r);
    pa[lson[id]]=id;
    pa[rson[id]]=id;
    return id;
}
void rmq_pre()
{
    for(int i=1;i<=n;i++)
    d[i][0]=num[i].a,rec[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i+j-1<=n;i++)
    {
        if(d[i][j-1]<d[i+(1<<(j-1))][j-1])
        {
            d[i][j]=d[i][j-1];
            rec[i][j]=rec[i][j-1];
        }
        else
        {
             d[i][j]=d[i+(1<<(j-1))][j-1];
            rec[i][j]=rec[i+(1<<(j-1))][j-1];
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&num[i].k,&num[i].a);
        num[i].index=i;
    }
    sort(num+1,num+n+1);
    rmq_pre();
    build(1,n);
    printf("YES\n");
    for(int i=1;i<=n;i++)
    printf("%d %d %d\n",pa[i],lson[i],rson[i]);
    return 0;
}