#include <bits/stdc++.h>

using namespace std;


typedef vector<int> vi;
typedef vector<bool> vb;


#define EB emplace_back
#define INF numeric_limits<int>::max()


struct Node {
    vi connected_nodes;  // stores their indices
};


// global variables:
int N, MAX_DEPTH = 5;
vector<Node> NODES;
vb PLAYER_MAX_MOVES;

int REAL_DUMB_MAX = 1;


// functions:
void input();
int Solve(vb player_moves_max, vb player_moves_min, int depth, bool maximisingPlayer, int alpha, int beta);

int cost(Node node);
int getMostConnectedNode();
vi getNewNodes(vb player_min, vb playe_max);

int main()
{
    freopen("input.txt", "r", stdin);

    input();
    int most_connected_node = getMostConnectedNode();
    PLAYER_MAX_MOVES[most_connected_node] = true;
    Solve(PLAYER_MAX_MOVES, vb(N), 1, false, -INF, -INF);
    printf("%d\n", REAL_DUMB_MAX);

    return 0;
}


int cost(vb player_moves) {   // calculate in how good position max player is
    int min_connected = INF;
    int max_connected = -INF;

    for (int i = 0; i < N; ++i) {
        if (player_moves[i]) {
            min_connected = min(min_connected, i);
            max_connected = max(max_connected, i);
        }
    }
    printf("ITS MIN: %d, max: %d\n", min_connected, max_connected);
    //REAL_DUMB_MAX = max(REAL_DUMB_MAX, max_connected);
    return max_connected - min_connected;
}


int Solve(vb player_moves_max, vb player_moves_min, int depth, bool maximisingPlayer, int alpha, int beta) {
    if (!depth || depth == MAX_DEPTH) return cost(player_moves_max);

    int sum = -INF;
    vi non_played_nodes = getNewNodes(player_moves_min, player_moves_max);

    if (maximisingPlayer) {
        for (int i = 0, n = non_played_nodes.size(); i < n; ++i) {
            player_moves_max[i] = true;
            sum = max(sum, Solve(player_moves_max, player_moves_min, depth - 1, false, alpha, beta));
            alpha = max(sum, alpha);
            if (alpha >= beta) {
                REAL_DUMB_MAX = max(REAL_DUMB_MAX, alpha);
                break;
            }  // terminate because optimal sol was found
        }
        return sum;
    }

    // minimising player:

    sum = INF;
    for (int i = 0, n = non_played_nodes.size(); i < n; ++i) {
        player_moves_min[i] = true;
        sum = min(sum, Solve(player_moves_max, player_moves_min, depth - 1, true, alpha, beta));
        beta = min(sum, beta);
        if (alpha >= REAL_DUMB_MAX) {
            REAL_DUMB_MAX = max(REAL_DUMB_MAX, beta);
            break;
        }
    }
    return sum;
}


int getMostConnectedNode(){
    int out = 0;
    int min_len = NODES[0].connected_nodes.size();
    int cur_len = NODES[0].connected_nodes.size();

    for (int i = 1; i < N; ++i) {
        cur_len = NODES[i].connected_nodes.size();
        if (min_len <= cur_len) {
            min_len = cur_len;
            out = i;
        }
    }

    return out;
}


vi getNewNodes(vb player_min, vb player_max) {
    vi out;

    for (int i = 0; i < N; ++i) {
        if (!player_min[i] && !player_max[i]) out.EB(i);
    }

    return out;
}


void input() {
    scanf("%d\n", &N);

    // allocate space and assign zeros:
    NODES.resize(N);
    PLAYER_MAX_MOVES.resize(N);

    int node_idx = -1;
    int connected_node = -1;
    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &node_idx, &connected_node);
        Node cur_node;
        cur_node.connected_nodes.EB(connected_node);
        NODES[node_idx] = cur_node;
    }
}