<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

218. Unstable Systems
time limit per test: 1.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Of course you know that some operating systems are not stable. Sasha learnt it only few days ago. Now there are very bad days of his life. He is an adminstrator of the network of n computers with different versions of such systems. Each computer is a workstation which is usually used to run a single program. But the programs often crash with a message "The system is busy or unstable" Sasha has determined some unsafety value corresponding to the frequency of program crash for each program on each workstation (the larger values correspond to more often crashes). Now he plans to arrange programs in such a way that the maximal unsafety value of all workstations will become minimal possible (because crashes slow down all the work!). Help him!

Input

The first line of the input file contains the number of workstations n (1 ≤ n ≤ 500) which is equal to number of programs. The next n lines contain n numbers each — j-th number of i-th line contains the unsafety value for a program j on i-th computer. All numbers do not exceed 106 by their absolute values.

Output

Write the maximal unsafety value on the first line. Then output n lines each corresponding to one program in format "i j" — i-th computer must run j-th program.

Sample test(s)

Input
2
1 3
4 5

Output
4
1 2
2 1
Author:	Andrew Stankevich, Andrew Lopatin
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-31

<|response|>
1. Abridged problem statement  
We have n computers and n programs, and an n×n matrix a where a[i][j] is the “unsafety” of running program j on computer i. We must assign exactly one program to each computer (a perfect matching) so that the maximum unsafety among all chosen pairs is as small as possible. Output that minimal maximum unsafety and one valid assignment.

2. Key observations  
- This is the classic “bottleneck assignment” problem: minimize the largest edge in a perfect matching of a complete bipartite graph.  
- Equivalently, ask: for a threshold T, can we select one entry in each row and column with value ≤ T? That becomes the question of whether a bipartite graph (rows vs. columns) with edges for all a[i][j] ≤ T has a perfect matching.  
- We can binary-search T over the sorted list of all n² values, and for each candidate T test if a perfect matching exists using Hopcroft–Karp in O(E√V).

3. Full solution approach  
a. Read n and the matrix a of size n×n.  
b. Flatten all entries into a list of triples (value, row, col) and sort it by value ascending. Call it edges.  
c. Binary search on an index mid in [0..n²−1]:  
   - Let threshold = edges[mid].value.  
   - Build a bipartite graph G(mid) with left nodes 0..n−1 (computers) and right nodes 0..n−1 (programs). Add an edge (i,j) if a[i][j] ≤ threshold (i.e. if (value, i, j) appears among the first mid+1 entries).  
   - Run Hopcroft–Karp on G(mid). If maximum matching size == n, we can lower the threshold (high = mid−1), else raise it (low = mid+1).  
d. After binary search, low (or the recorded answer index) gives the smallest threshold that admits a perfect matching. Rebuild G(answer) and run Hopcroft–Karp one more time to extract an explicit matching.  
e. Output the threshold and the n matched pairs, converting indices to 1-based.

Time complexity:  
- Sorting edges in O(n² log(n²)).  
- Each matching check in O(E√V)=O(n²√n).  
- O(log(n²))≈O(log n) checks. Total ≈ O(n²√n log n), feasible for n≤500.

4. C++ Solution
```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/maxflow.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class HopcroftKarp {
  private:
    int n, m;
    vector<int> dist;

    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for(int u = 0; u < n; ++u) {
            if(inv_match[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }

        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                int m = match[v];
                if(m == -1) {
                    found = true;
                } else if(dist[m] == -1) {
                    dist[m] = dist[u] + 1;
                    q.push(m);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        for(int v: adj[u]) {
            int m = match[v];
            if(m == -1 || (dist[m] == dist[u] + 1 && dfs(m))) {
                inv_match[u] = v;
                match[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

  public:
    vector<int> match, inv_match;
    vector<vector<int>> adj;

    HopcroftKarp(int _n, int _m = -1) : n(_n), m(_m == -1 ? _n : _m) {
        adj.assign(n, vector<int>());
        clear(false);
    }

    void clear(bool clear_adj = true) {
        match.assign(m, -1);
        inv_match.assign(n, -1);
        if(clear_adj) {
            adj.assign(n, vector<int>());
        }
    }

    void add_edge(int u, int v) { adj[u].push_back(v); }

    int max_matching(bool shuffle_edges = false) {
        if(shuffle_edges) {
            for(int i = 0; i < n; i++) {
                shuffle(
                    adj[i].begin(), adj[i].end(),
                    mt19937(
                        chrono::steady_clock::now().time_since_epoch().count()
                    )
                );
            }
        }

        int ans = 0;
        while(bfs()) {
            for(int u = 0; u < n; ++u) {
                if(inv_match[u] == -1 && dfs(u)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    vector<pair<int, int>> get_matching() {
        vector<pair<int, int>> matches;
        for(int u = 0; u < n; ++u) {
            if(inv_match[u] != -1) {
                matches.emplace_back(u, inv_match[u]);
            }
        }
        return matches;
    }

    pair<vector<int>, vector<int>> minimum_vertex_cover() {
        vector<int> left_cover, right_cover;
        bfs();

        for(int u = 0; u < n; ++u) {
            if(dist[u] == -1) {
                left_cover.push_back(u);
            }
        }

        for(int v = 0; v < m; ++v) {
            if(match[v] != -1 && dist[match[v]] != -1) {
                right_cover.push_back(v);
            }
        }

        return {left_cover, right_cover};
    }
};

using BipartiteMatching = HopcroftKarp;

int n;
vector<vector<int>> a;

void read() {
    cin >> n;
    a.assign(n, vector<int>(n));
    cin >> a;
}

BipartiteMatching eval(int mid, const vector<array<int, 3>>& edges) {
    vector<array<int, 3>> edges2;
    for(auto [w, u, v]: edges) {
        if(w <= edges[mid][0]) {
            edges2.push_back({w, u, v});
        }
    }

    int m = edges2.size();
    BipartiteMatching bm(n);
    for(auto [w, u, v]: edges2) {
        bm.add_edge(u, v);
    }

    return bm;
}

void solve() {
    // We want to assign programs to workstations (a perfect matching of an
    // n x n bipartite graph) minimizing the maximum used unsafety value. Sort
    // all n^2 (value, computer, program) entries and binary search on the
    // threshold index mid: keeping only edges with value <= edges[mid][0], a
    // perfect matching of size n exists iff the threshold is feasible. Feasible
    // thresholds are monotone, so we binary search for the smallest one using
    // Hopcroft-Karp to test for a perfect matching, then rebuild the matching at
    // the answer threshold and print the pairing.

    vector<array<int, 3>> edges;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            edges.push_back({a[i][j], i, j});
        }
    }

    sort(edges.begin(), edges.end());

    int low = 0, high = n * n - 1, ans = -1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(eval(mid, edges).max_matching(true) == n) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    BipartiteMatching bm = eval(ans, edges);
    bm.max_matching();
    cout << edges[ans][0] << '\n';
    auto matching = bm.get_matching();
    for(auto [u, v]: matching) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
from collections import deque

def hopcroft_karp(adj, N, M):
    # adj: list of lists, adj[u] = list of v's
    # N = number of left nodes, M = number of right nodes
    INF = 10**9
    pairU = [-1]*N    # pairU[u] = matched v or -1
    pairV = [-1]*M    # pairV[v] = matched u or -1
    dist = [0]*N

    def bfs():
        queue = deque()
        for u in range(N):
            if pairU[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = INF
        found = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                pu = pairV[v]
                if pu == -1:
                    found = True
                elif dist[pu] == INF:
                    dist[pu] = dist[u] + 1
                    queue.append(pu)
        return found

    def dfs(u):
        for v in adj[u]:
            pu = pairV[v]
            if pu == -1 or (dist[pu] == dist[u] + 1 and dfs(pu)):
                pairU[u] = v
                pairV[v] = u
                return True
        dist[u] = INF
        return False

    matching = 0
    while bfs():
        for u in range(N):
            if pairU[u] == -1 and dfs(u):
                matching += 1
    return matching, pairU

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]

    # Flatten and sort edges (value, row, col)
    edges = []
    for i in range(n):
        for j in range(n):
            edges.append((a[i][j], i, j))
    edges.sort(key=lambda x: x[0])

    # Build adjacency list up to index mid
    def build_adj(mid):
        adj = [[] for _ in range(n)]
        for k in range(mid+1):
            _, i, j = edges[k]
            adj[i].append(j)
        return adj

    # Binary search on sorted edges
    low, high, answer = 0, n*n-1, n*n-1
    while low <= high:
        mid = (low + high) // 2
        adj = build_adj(mid)
        match_size, _ = hopcroft_karp(adj, n, n)
        if match_size == n:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1

    # Reconstruct final assignment
    adj = build_adj(answer)
    _, pairU = hopcroft_karp(adj, n, n)
    bestT = edges[answer][0]

    # Output
    out = [str(bestT)]
    for i in range(n):
        # computer i runs program pairU[i]
        out.append(f"{i+1} {pairU[i]+1}")
    print("\n".join(out))

if __name__ == "__main__":
    main()
```