#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
#include "minerals.h"
void Solve(int N) {
vector <int> gs_l;
vector <int> gs_r;
int cnt = 0;
for (int i = 1; i <= 2 * N; ++i) {
int cur_cnt = Query(i);
if (cur_cnt > cnt) {
cnt = cur_cnt;
gs_l.push_back(i);
} else {
gs_r.push_back(i);
Query(i);
}
}
vector <int> f, s;
function <void(vector <int>, vector <int>, int, int)> rec = [&] (vector <int> l, vector <int> r, int em_l, int em_r) {
/*cout << em_r << endl;
cout << "start\n";
for (int x : l) {
cout << x << ' ';
}
cout << endl;
for (int x : r) {
cout << x << ' ';
}
cout << endl << "finish" << endl;
Print();*/
if (l.size() == 1) {
assert(r.size() == 1);
f.push_back(l[0]);
s.push_back(r[0]);
} else {
int m = (int)l.size() / 2;
vector <int> l_l, l_r, r_l, r_r;
for (int i = 0; i < m; ++i) l_l.push_back(l[i]);
for (int i = m; i < (int)l.size(); ++i) l_r.push_back(l[i]);
int have = -1;
for (auto x : l_l) {
have = Query(x);
}
if (!em_l) {
for (auto x : r) {
int cur = Query(x);
if (cur != have) {
r_l.push_back(x);
} else {
r_r.push_back(x);
}
have = cur;
}
rec(l_l, r_l, 1, em_r ^ 1);
rec(l_r, r_r, 0, em_r ^ 1);
} else {
for (auto x : r) {
int cur = Query(x);
if (cur != have) {
r_r.push_back(x);
} else {
r_l.push_back(x);
}
have = cur;
}
rec(l_l, r_l, 0, em_r ^ 1);
rec(l_r, r_r, 1, em_r ^ 1);
}
}
};
rec(gs_l, gs_r, 0, 1);
for (int i = 0; i < N; ++i) {
Answer(f[i], s[i]);
}
}
#ifdef LOCAL
constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 1000000;
namespace {
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
int N;
int _counterpart[2 * MAX_N + 1];
int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int _count[2 * MAX_N + 1];
int num_answers;
int answer[2 * MAX_N + 1];
} // namespace
int Query(int x) {
if (!(1 <= x && x <= 2 * N)) {
WrongAnswer(1);
}
/*if (++num_queries > MAX_CALLS) {
WrongAnswer(2);
}*/
++num_queries;
const int type = std::min(x, _counterpart[x]);
if (on[x]) {
--on[x];
--_count[type];
if (_count[type] == 0) {
--num_kinds;
}
} else {
++on[x];
++_count[type];
if (_count[type] == 1) {
++num_kinds;
}
}
return num_kinds;
}
void Answer(int a, int b) {
if (++num_answers > N) {
WrongAnswer(6);
}
if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
WrongAnswer(3);
}
if (answer[a] != 0) {
WrongAnswer(4);
}
answer[a] = b;
if (answer[b] != 0) {
WrongAnswer(4);
}
answer[b] = a;
if (!(_counterpart[a] == b && _counterpart[b] == a)) {
WrongAnswer(5);
}
}
void Print() {
cout << "Start printing\n";
for (int i = 1; i <= 2 * N; ++i) {
if (on[i]) {
cout << i << ' ';
}
}
cout << endl;
cout << "End printing\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> N;
for (int i = 1; i <= N; ++i) {
int x, y;
cin >> x >> y;
_counterpart[x] = y;
_counterpart[y] = x;
}
Solve(N);
if (num_answers != N) {
WrongAnswer(6);
}
printf("Accepted: %d\n", num_queries);
return 0;
}
#endif
