#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int PP=(1<<17);
//#warning small constants
//const int N=4;
//const int PP=4;
pair<int,int> tab[N+10];
vector<int> cup[2][N+10];
int cnt[N+10];
int tree[2*PP+10];
bool ok[2*PP+10];
// sat
// 2*id - var, 2*id+1 - !var
int var[2][N+10];
int neg(int x)
{
return (x%2==0 ? x+1:x-1);
}
vector<vector<int>> e;
int new_var()
{
for(int i:{0,1})
e.push_back({});
return e.size()-2;
}
void new_clause(int a,int b)
{
//auto debwr=[](int x){ if(x%2==0) cerr<<x<<" "; else cerr<<"!"<<x-1<<" "; return; };
//debwr(a); cerr<<"or "; debwr(b); cerr<<"\n";
e[neg(a)].push_back(b);
e[neg(b)].push_back(a);
return;
}
vector<int> low;
vector<int> pre;
vector<bool> val;
vector<bool> vis;
vector<bool> on_stack;
vector<int> scc;
vector<int> stck;
vector<int> topo;
void dfs1(int x)
{
static int nr=0,sccnr=0;
vis[x]=true;
stck.push_back(x);
on_stack[x]=true;
pre[x]=nr++;
low[x]=pre[x];
for(auto v:e[x])
{
if(on_stack[v])
low[x]=min(low[x],pre[v]);
else if(!vis[v])
{
dfs1(v);
low[x]=min(low[x],low[v]);
}
}
if(low[x]==pre[x])
{
while(on_stack[x])
{
int v=stck.back();
stck.pop_back();
scc[v]=sccnr;
on_stack[v]=false;
}
sccnr++;
}
return;
}
void dfs2(int x)
{
vis[x]=true;
for(auto v:e[x])
{
if(!vis[v])
dfs2(v);
}
if(low[x]==pre[x])
topo.push_back(x);
return;
}
void dfs3(int x)
{
vis[x]=true;
val[scc[neg(x)]]=!val[scc[x]];
for(auto v:e[x])
{
if(!vis[v])
{
if(scc[v]==scc[x])
dfs3(v);
else if(val[scc[x]])
val[scc[v]]=true;
}
}
return;
}
vector<bool> solve_2sat()
{
int n=e.size();
for(auto *vec:{&low,&pre,&scc})
vec->resize(n);
for(auto *vec:{&val,&vis,&on_stack})
{
vec->resize(n);
fill(vec->begin(),vec->end(),false);
}
for(int i=0;i<n;i++)
{
if(!vis[i])
dfs1(i);
}
fill(vis.begin(),vis.end(),false);
for(int i=0;i<n;i++)
{
if(!vis[i])
dfs2(i);
}
reverse(topo.begin(),topo.end());
fill(vis.begin(),vis.end(),false);
for(auto v:topo)
{
dfs3(v);
}
//for(int i=0;i<n;i++)
// cerr<<"scc["<<i<<"]="<<scc[i]<<" "<<val[scc[i]]<<"\n";
vector<bool> ans(n,false);
for(int i=0;i<n;i++)
{
if(val[scc[i]]==val[scc[neg(i)]])
return {};
for(auto v:e[i])
{
if(val[scc[i]] && !val[scc[v]])
return {};
}
ans[i]=val[scc[i]];
}
return ans;
}
void new_node(int x)
{
if(!ok[2*x] && !ok[2*x+1])
{
ok[x]=false;
tree[x]=-1;
return;
}
ok[x]=true;
if(!ok[2*x])
{
tree[x]=tree[2*x+1];
return;
}
if(!ok[2*x+1])
{
tree[x]=tree[2*x];
return;
}
tree[x]=new_var();
new_clause(neg(tree[2*x]),tree[x]);
new_clause(neg(tree[2*x+1]),tree[x]);
return;
}
void add_segment(int l,int r,int c)
{
for(l+=PP-1,r+=PP-1;l<=r;l/=2,r/=2)
{
if(l%2==1)
{
if(ok[l])
new_clause(neg(c),neg(tree[l]));
l++;
}
if(r%2==0)
{
if(ok[r])
new_clause(neg(c),neg(tree[r]));
r--;
}
}
return;
}
void upd_node(int x,int c)
{
x+=PP-1;
ok[x]=(c!=-1);
tree[x]=c;
for(x/=2;x>0;x/=2)
new_node(x);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tab[i].fi>>tab[i].se;
cup[0][tab[i].fi].push_back(i);
cup[1][tab[i].se].push_back(i);
}
for(int i=1;i<=N;i++)
{
var[0][i]=-1;
var[1][i]=-1;
}
for(int i=1;i<=n;i++)
{
if(var[0][tab[i].fi]==-1)
var[0][tab[i].fi]=new_var();
if(var[1][tab[i].se]==-1)
var[1][tab[i].se]=new_var();
if(cup[0][tab[i].fi].size()==1 && cup[1][tab[i].se].size()==1)
{
cout<<"NE\n";
return 0;
}
else if(cup[0][tab[i].fi].size()==1)
new_clause(var[1][tab[i].se],var[1][tab[i].se]);
else if(cup[1][tab[i].se].size()==1)
new_clause(var[0][tab[i].fi],var[0][tab[i].fi]);
else
{
new_clause(var[0][tab[i].fi],var[1][tab[i].se]);
new_clause(neg(var[0][tab[i].fi]),neg(var[1][tab[i].se]));
}
}
for(int i=PP;i<2*PP;i++)
{
tree[i]=-1;
ok[i]=false;
}
for(int i=PP-1;i>0;i--)
new_node(i);
for(int i=1;i<=N;i++)
{
if(cup[1][i].size()==2)
{
int l=cup[1][i][0],r=cup[1][i][1];
l=tab[l].fi;
r=tab[r].fi;
if(l>r)
swap(l,r);
add_segment(l,r,var[1][i]);
}
for(auto v:cup[1][i])
{
v=tab[v].fi;
if(cnt[v]==0)
upd_node(v,var[0][v]);
else
upd_node(v,-1);
cnt[v]++;
}
}
//for(int i=1;i<=N;i++)
//{
// cerr<<"fi="<<i<<": "<<var[0][i]<<"\n";
// cerr<<"se="<<i<<": "<<var[1][i]<<"\n";
//}
auto ans=solve_2sat();
if(ans.empty())
{
cout<<"NE\n";
return 0;
}
cout<<"DA\n";
for(int i=1;i<=N;i++)
{
for(int j:{0,1})
{
if(cup[j][i].size()==2 && ans[var[j][i]])
cout<<cup[j][i][0]<<" "<<cup[j][i][1]<<"\n";
}
}
return 0;
}
