#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

const int MAX_N = 1 << 20;

// セグメント木を持つグローバル配列
int n_even, n_odd, dat_even[2 * MAX_N - 1], dat_odd[2 * MAX_N - 1];

// 初期化
void init_even(int n_){
    // 簡単のため要素数を2のべき乗に
    n_even = 1;
    while(n_even < n_)n_even *= 2;

    // 全ての値をINT_MAXに
    for(int i = 0; i < 2 * n_even - 1; i++)dat_even[i] = INT_MAX;
}

// 初期化
void init_odd(int n_){
    // 簡単のため要素数を2のべき乗に
    n_odd = 1;
    while(n_odd < n_)n_odd *= 2;

    // 全ての値をINT_MAXに
    for(int i = 0; i < 2 * n_odd - 1; i++)dat_odd[i] = INT_MAX;
}

// k番目の値(0-indexed)をaに変更
void update_even(int k, int a){
    // 葉の接点
    k += n_even - 1;
    dat_even[k] = a;
    // 登りながら更新
    while(k > 0){
        k = (k - 1) / 2;
        dat_even[k] = min(dat_even[k * 2 + 1], dat_even[k * 2 + 2]);
    }
}

// k番目の値(0-indexed)をaに変更
void update_odd(int k, int a){
    // 葉の接点
    k += n_odd - 1;
    dat_odd[k] = a;
    // 登りながら更新
    while(k > 0){
        k = (k - 1) / 2;
        dat_odd[k] = min(dat_odd[k * 2 + 1], dat_odd[k * 2 + 2]);
    }
}

// [a,b)の最小値を求める
// 後ろのほうの引数は、計算の簡単のための引数。
// kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
// したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
int query_even(int a, int b, int k, int l, int r){
    // [a, b)と[l, r)が交差しなければ、INT_MAX
    if (r <= a || b <= l)return INT_MAX;

    // [a, b)が[l, r)を完全に含んでいれば、この節点の値
    if (a <= l && r <= b)return dat_even[k];
    else {
        // そうでなければ、2つの子の最小値
        int vl = query_even(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query_even(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

// [a,b)の最小値を求める
// 後ろのほうの引数は、計算の簡単のための引数。
// kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
// したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
int query_odd(int a, int b, int k, int l, int r){
    // [a, b)と[l, r)が交差しなければ、INT_MAX
    if (r <= a || b <= l)return INT_MAX;

    // [a, b)が[l, r)を完全に含んでいれば、この節点の値
    if (a <= l && r <= b)return dat_odd[k];
    else {
        // そうでなければ、2つの子の最小値
        int vl = query_odd(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query_odd(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

vector<pair<int,int>> ans;
int aikata[MAX_N * 2 + 1];
int arg_count_[MAX_N * 2 + 1];
int f[MAX_N * 2 + 1] = {};
int n;
int count_ = 0;
vector<int> G[MAX_N * 2 + 1];

void dfs(int query, int l, int r, int x, int par){
    // cout << query << ' ' << l << ' ' << r << endl;
    // int aaa; cin >> aaa;
    if(query == 0 && l < r){ // 最小値探し.
        if(l % 2 == 0){
            // cout << (r-1)/2 << endl;
            int mi1 = query_even(l/2, (r-1)/2+1, 0, 0, n/2);
            int mi2 = query_odd(l/2, (r-1)/2+1, 0, 0, n/2);
            if(mi1 < mi2){
                // cout << "mi1" << ' ' << mi1 << endl;
                if(l < f[mi1]-1)dfs(0, l, f[mi1]-1, -1, par);
                dfs(1,f[mi1]+1,r,mi1, par);
            }else{
                if(f[mi2]+1<r)dfs(0,f[mi2]+1,r,-1, par);
                dfs(2,l,f[mi2]-1,mi2, par);
            }
        }else{
            int mi1 = query_odd((l-1)/2, r/2-1+1, 0, 0, n/2);
            int mi2 = query_even((l-1)/2+1, r/2+1, 0, 0, n/2);
            if(mi1 < mi2){
                if(l < f[mi1]-1)dfs(0, l, f[mi1]-1, -1, par);
                dfs(1,f[mi1]+1,r,mi1, par);
            }else{
                if(f[mi2]+1 < r)dfs(0,f[mi2]+1,r,-1, par);
                dfs(2,l,f[mi2]-1,mi2, par);
            }
        }
    }
    if(query == 1){ // 後ろ探し.
        if(l % 2 == 1){
            int mi = query_odd((l-1)/2, (r-1)/2+1, 0, 0, n/2);
            ans.push_back(P(x,mi));
            count_++;
            G[par].push_back(count_);
            if(l < f[mi]-1)dfs(0, l, f[mi]-1, -1, count_);
            if(f[mi]+1 < r)dfs(0, f[mi]+1, r, -1, par);
        }else{
            int mi = query_even(l/2, r/2+1, 0, 0, n/2);
            ans.push_back(P(x,mi));
            count_++;
            G[par].push_back(count_);
            if(l < f[mi]-1)dfs(0, l, f[mi]-1, -1, count_);
            if(f[mi]+1 < r)dfs(0, f[mi]+1, r, -1, par);
        }
    }
    if(query == 2){ // 前探し.
        if(l % 2 == 0){
            int mi = query_even(l/2, r/2+1, 0, 0, n/2);
            ans.push_back(P(mi,x));
            count_++;
            int count__ = count_;
            G[par].push_back(count_);
            if(l < f[mi]-1)dfs(0, l, f[mi]-1, -1, par);
            if(f[mi]+1 < r)dfs(0, f[mi]+1, r, -1, count__);
        }else{
            int mi = query_odd((l-1)/2, (r-1)/2+1, 0, 0, n/2);
            ans.push_back(P(mi,x));
            count_++;
            int count__ = count_;
            G[par].push_back(count_);
            if(l < f[mi]-1)dfs(0, l, f[mi]-1, -1, par);
            if(f[mi]+1 < r)dfs(0, f[mi]+1, r, -1, count__);
        }
    }
}

int main(){
    cin >> n;
    init_even(n / 2);
    init_odd(n / 2);
    int nn = n;
    n = n_even * 2;
    int p[nn];
    rep(i,nn / 2){
        cin >> p[i*2] >> p[i*2+1];
        // cout << i << ' ' << p[i*2] << endl;
        update_even(i, p[i*2]);
        // cout << i << ' ' << query_even(i,i+1,0,0,n/2) << endl;
        update_odd(i, p[i*2+1]);
        f[p[i*2]] = i*2;
        f[p[i*2+1]] = i*2+1;
    }
    /*
    cout << n_even << ' ' << n_odd << endl;
    rep(i,nn/2){
       cout << i << ' ' << query_even(i,i+1,0,0,n/2) << endl;
    }
    */

    dfs(0, 0, nn-1, -1, 0);

    rep(i,nn/2){
        aikata[ans[i].first] = ans[i].second;
        arg_count_[ans[i].first] = i + 1;
    }
    
    priority_queue<int> que;
    rep(i, G[0].size()){
        que.push(-ans[G[0][i]-1].first);
    }

    while(que.size() > 0){
        int x = -que.top();
        que.pop();
        cout << x << ' ' << aikata[x] << ' ';
        rep(i,G[arg_count_[x]].size()){
            que.push(-ans[G[arg_count_[x]][i]-1].first);
        }
    }
       
    cout << endl;

    return 0;
}


Measured memory_bytes: 81140