#include <bits/stdc++.h>
using namespace std;
ifstream inputFile("harta.in");
ofstream outputFile("harta.out");
// Matrice de capacități și matrice de fluxuri
int capacityMatrix[1001][1001], flowMatrix[1001][1001];
// Vector pentru a stoca părinții în timpul BFS
vector<int> parentVector;
// Listă de adiacență pentru a reprezenta graful
vector<int> adjacencyList[1001];
int numberOfCities;
// BFS pentru a găsi căi de creștere
int bfs(int start, int end) {
// Folosim o coadă și un vector de vizitare
deque<int> queue;
vector<bool> visited(end + 1, false);
// Inițializăm vectorul de părinți
parentVector.assign(end + 1, 0);
queue.push_back(start);
visited[start] = true;
while (!queue.empty()) {
int currentNode = queue.front();
queue.pop_front();
// Dacă am ajuns la destinație, ieșim din BFS
if (currentNode == end) break;
// Parcurgem vecinii nodului curent
for (int i = 0; i < adjacencyList[currentNode].size(); i++) {
int neighbor = adjacencyList[currentNode][i];
// Dacă capacitatea muchiei este mai mare decât fluxul curent
// Adăugăm nodul în coadă
if (!visited[neighbor] && capacityMatrix[currentNode][neighbor] > flowMatrix[currentNode][neighbor]) {
queue.push_back(neighbor);
// Păstrăm nodul anterior în vectorul de părinți
// Pentru a reconstrui calea ulterior
parentVector[neighbor] = currentNode;
visited[neighbor] = true;
}
}
}
// Dacă am ajuns la destinație (am găsit o cale de creștere), returnăm 1
// Altfel, returnăm 0
if (parentVector[end]) return 1;
return 0;
}
// Algoritmul lui Edmonds-Karp pentru a găsi fluxul maxim
int edmondsKarp(int start, int end) {
int maxFlow = 0;
int current, minFlow;
while (bfs(start, end)) {
minFlow = INT_MAX;
current = end;
// Determinăm fluxul minim pe calea de creștere,
// Comparând fluxul dintre nodul curent și părintele său cu fluxul minim curent
while (current != 0) {
if ((capacityMatrix[parentVector[current]][current] - flowMatrix[parentVector[current]][current]) < minFlow)
minFlow = (capacityMatrix[parentVector[current]][current] - flowMatrix[parentVector[current]][current]);
current = parentVector[current];
}
current = end;
// Actualizăm fluxurile pe cale
while (current != 0) {
// Fluxul crește pe muchiile directe și scade pe cele inverse
flowMatrix[parentVector[current]][current] += minFlow;
flowMatrix[current][parentVector[current]] -= minFlow;
current = parentVector[current];
}
// Adăugăm fluxul minim la fluxul total
maxFlow += minFlow;
}
return maxFlow;
}
int main() {
int startNode, endNode, outDegree, inDegree;
inputFile >> numberOfCities;
startNode = 0;
endNode = numberOfCities + numberOfCities + 1;
// Construim graf și matricea de capacități
for (int city = 1; city <= numberOfCities; city++) {
inputFile >> outDegree >> inDegree;
adjacencyList[startNode].push_back(city);
adjacencyList[city].push_back(startNode);
capacityMatrix[startNode][city] = outDegree;
int auxiliaryNode = numberOfCities + city;
adjacencyList[auxiliaryNode].push_back(endNode);
adjacencyList[endNode].push_back(auxiliaryNode);
capacityMatrix[auxiliaryNode][endNode] = inDegree;
}
// Adăugăm muchii între orașe cu constrângerile specificate
// 1. nu putem merge din oras in el insusi
// 2. nu putem avea muchia i-j daca avem deja muchia j-i
for (int city1 = 1; city1 <= numberOfCities; city1++) {
for (int city2 = numberOfCities + 1; city2 <= numberOfCities + numberOfCities; city2++) {
if ((city1 % numberOfCities) != (city2 % numberOfCities)) {
adjacencyList[city1].push_back(city2);
adjacencyList[city2].push_back(city1);
capacityMatrix[city1][city2] = 1;
}
}
}
// Găsim și afișăm fluxul maxim
outputFile << edmondsKarp(startNode, endNode) << endl;
// Afișăm drumurile selectate în fluxul maxim
for (int city1 = 1; city1 <= numberOfCities; city1++) {
for (int city2 = numberOfCities + 1; city2 <= numberOfCities + numberOfCities; city2++) {
if (flowMatrix[city1][city2] == 1)
outputFile << city1 << ' ' << city2 - numberOfCities << endl;
}
}
inputFile.close();
outputFile.close();
return 0;
}