#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
using namespace std;
int x[N], y[N], a[N][2], b[N], n, xr[N], yr[N];
set <int> alone;
set <pair <int, int> > ty_del[N * 4];
vector <pair <int, int> > psh_dely[N * 4];
bool mk[N], mkr[N][2];
vector <pair <int, int> > g;
void Push_dely(int v, int tl, int tr)
{
while (sz(psh_dely[v]) > 0)
{
pair <int, int> pt = psh_dely[v].back();
psh_dely[v].pop_back();
ty_del[v].insert(pt);
if (tl != tr) {psh_dely[v + v].pb(pt); psh_dely[v + v + 1].pb(pt); }
}
}
void upd_del(int v, int tl, int tr, int l, int r, pair <int, int> val)
{
if (tl > tr || l > r || r < tl || tr < l) return;
if (l <= tl && tr <= r) {psh_dely[v].pb(val); return;}
int md = (tl + tr) >> 1;
upd_del(v + v, tl, md, l, r, val);
upd_del(v + v + 1, md + 1, tr, l, r, val);
}
void add_remove(int fr, int sc)
{
if (!mk[fr]) {if (a[fr][1] != -1) adder(fr); else {cout << "NE" << endl; exit(0);}}
if (!mk[sc]) {if (a[sc][1] != -1) adder(sc); else {cout << "NE" << endl; exit(0);}}
}
void good_del(int v, int tl, int tr, int pos, int l, int r)
{
Push_dely(v, tl, tr);
if (tl == tr)
{
set <pair <int, int> > :: iterator it;
it = ty_del[v].lower_bound({l, -1e9});
while (it != ty_del[v].end() && (*it).F <= r) {add_remove(b[(*it).S], (*it).S); it++;}
}
else
{
int md = (tl + tr) >> 1;
if (pos <= md) good_del(v + v, tl, md, pos, l, r);
else good_del(v + v + 1, md + 1, tr, pos, l, r);
}
}
void seacrh(int fr, int sc)
{
if (x[fr] > x[sc]) swap(fr, sc);
good_del(1, 1, N, y[fr], x[fr], x[sc]);
}
void add(int fr, int sc)
{
g.pb({fr, sc});
seacrh(fr, sc);
}
void adder(int v)
{
if (mk[v]) return;
if (a[v][1] != -1) {mk[v] = 1; mk[a[v][1]] = 1; add(v, a[v][1]); return;}
cout << "NE" << endl;
exit(0);
}
void fnd()
{
while (sz(alone) > 0)
{
int v = *alone.begin();
alone.erase(alone.begin());
adder(v);
}
for (int i = 0; i < n; i++)
{
if (mk[i]) continue;
g.pb({i, a[i][0]});
mk[a[i][0]] = 1;
}
}
void add_del(int fr, int sc)
{
if (mkr[fr][0]) return;
mkr[fr][0] = 1;
mkr[sc][0] = 1;
if (y[fr] > y[sc]) swap(fr, sc);
upd_del(1, 1, N, y[fr], y[sc], {x[fr], fr });
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < N; i++) xr[i] = yr[i] = -1;
for (int i = 0; i < n; i++) {cin >> x[i] >> y[i]; a[i][0] = a[i][1] = -1;}
for (int i = 0; i < n; i++)
{
int X = x[i], Y = y[i];
if (xr[X] == -1) xr[X] = i; else {a[i][0] = xr[X]; a[xr[X]][0] = i;}
if (yr[Y] == -1) yr[Y] = i; else {a[i][1] = yr[Y]; a[yr[Y]][1] = i;}
}
for (int i = 0; i < n; i++)
{
b[i] = a[i][0];
if (a[i][0] == a[i][1] && a[i][1] == -1) {cout << "NE" << endl; exit(0);}
if (a[i][0] != -1) add_del(i, a[i][0]);
}
for (int i = 0; i < n; i++) if (a[i][0] == -1) adder(i);
fnd();
if (sz(g) != n / 2) {cout << "NE" << endl; exit(0);}
cout << "DA" << endl;
for (auto it : g) cout << it.F + 1 << " " << it.S + 1 << endl;
}
Compilation message
matching.cpp: In function 'void add_remove(int, int)':
matching.cpp:58:40: error: 'adder' was not declared in this scope
if (!mk[fr]) {if (a[fr][1] != -1) adder(fr); else {cout << "NE" << endl; exit(0);}}
^~~~~
matching.cpp:60:40: error: 'adder' was not declared in this scope
if (!mk[sc]) {if (a[sc][1] != -1) adder(sc); else {cout << "NE" << endl; exit(0);}}
^~~~~
