#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include "tree2.h"
using namespace std;

struct segtree {
    int tree[262144];
    int ind[262144];
    void update(int v, int l, int r, int ql, int qr, int val, int index) {
        if(l>qr || r<ql) return;
        if(l>=ql && r<=qr) {
            if(tree[v]<val) {
                tree[v]=val;
                ind[v]=index;
            }
            return;
        }
        int mid = (l+r)>>1;
        update(v<<1, l, mid, ql, qr, val, index);
        update(v<<1|1, mid+1, r, ql, qr, val, index);
        if(tree[v<<1]>tree[v<<1|1]) {
            tree[v]=tree[v<<1];
            ind[v]=ind[v<<1];
        }
        else {
            tree[v]=tree[v<<1|1];
            ind[v]=ind[v<<1|1];
        }
    }
    pair<int,int> query(int v, int l, int r, int ql, int qr) {
        if(l>qr || r<ql) return {0, 0};
        if(l>=ql && r<=qr) return {tree[v], ind[v]};
        int mid = (l+r)>>1;
        return max(query(v<<1, l, mid, ql, qr), query(v<<1|1, mid+1, r, ql, qr));
    }
} listree, ldstree;
int p[100000];
unordered_map<int, vector<int>> v;
bool usedval[100000];
int backi[100000];
int backd[100000];
int lis[100000];
int lds[100000];
int t=1;
int sq;
unordered_map<int,int> m;

void dfs(int i, int par) {
    p[t]=i;
    t++;
    for(auto &x : v[i]) {
        if(x==par) continue;
        dfs(x, i);
    }
}

vector<int> encode(int n, vector<pair<int, int>> v) {
    ::v.clear();
    t=1;
    m.clear();
    sq=(int)sqrt(n);
    
    vector<int> ans;

    for(auto &x : v) {
        ::v[x.first].push_back(x.second);
        ::v[x.second].push_back(x.first);
    }
    dfs(1, 0);
    
    int mxl=0, mxd=0;
    for(int i = 1; i <= n; i++) {
        auto q = listree.query(1, 1, n, 1, p[i]-1);
        listree.update(1, 1, n, p[i], p[i], q.first+1, i);
        backi[i]=q.second;
        lis[i]=q.first+1;
        if(lis[i]>lis[mxl]) mxl=i;
    }

    for(int i = 1; i <= n; i++) {
        auto q = ldstree.query(1, 1, n, p[i]+1, n);
        ldstree.update(1, 1, n, p[i], p[i], q.first+1, i);
        backd[i]=q.second;
        lds[i]=q.first+1;
        if(lds[i]>lds[mxd]) mxd=i;
    }

    if(lis[mxl]>=sq) {
        // l - izbirame sqrt
        while(mxl!=0 && ans.size()<sq) {
            ans.push_back(p[mxl]);
            mxl=backi[mxl];
        }
    }
    else {
        // r - izbirame sqrt+1
        while(mxd!=0 && ans.size()<sq+1) {
            ans.push_back(p[mxd]);
            mxd=backd[mxd];
        }
    }

    return ans;
}

vector<pair<int, int>> decode(int n, vector<pair<int, int>> v) {
    ::v.clear();
    t=1;
    m.clear();
    sq=(int)sqrt(n);

    for(auto &x : v) {
        ::v[x.first].push_back(x.second);
        ::v[x.second].push_back(x.first);
    }
    bool rootBlock=1;
    for(auto &x : v) {
        if(x.first==1||x.second==1) rootBlock=0;
    }
    dfs(rootBlock?-1:1, 0);
    
    int br=0, ptr=1;
    for(int i = 1; i <= n; i++) {
        br+=(p[i]<0);
        if(p[i]>0) usedval[p[i]]=1;
    }

    if(br==sq) {
        // lis
        for(int i = 1; i <= n; i++) {
            if(p[i]>0) usedval[p[i]]=1;
            else {
                while(usedval[ptr]) ptr++;
                m[p[i]]=ptr;
                usedval[ptr]=1;
            }
        }
    }
    else {
        // lds
        ptr=n;
        for(int i = 1; i <= n; i++) {
            if(p[i]>0) usedval[p[i]]=1;
            else {
                while(usedval[ptr]) ptr--;
                m[p[i]]=ptr;
                usedval[ptr]=1;
            }
        }
    }

    vector<pair<int,int>> ans;
    for(auto &x : v) {
        ans.push_back({x.first<0?m[x.first]:x.first, x.second<0?m[x.second]:x.second});
    }
    return ans;
}