#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5;
pair<int,int> p[maxn];
map<pair<int,int>, int> mp,e,bench;
int k,used[maxn];
int in;
vector<int> v,u,a,b;
void dfs(int i,int l)
{
//cout<<i<<endl;
in++;
if(i!=1)
{
v.push_back(l);
u.push_back(i);
e[{i,l}]=e[{l,i}]=1;
}
used[i]=1;
pair<int,int> c;
c=p[i];c.first+=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];c.first-=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];c.second+=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];c.second-=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
}
int construct_roads(std::vector<int> x, std::vector<int> y)
{
mp.clear();
e.clear();
v.clear();
u.clear();
a.clear();
b.clear();
memset(used,0,sizeof(used));
in=0;
k=x.size();
for(int i=0;i<k;i++)
{
p[i+1]={x[i],y[i]};
mp[p[i+1]]=i+1;
}
dfs(1,0);
if(in!=k)return 0;
for(int i=0;i<k-1;i++)
{
pair<int,int> p1=p[v[i]],p2=p[u[i]];
if(p1.first==p2.first)
{
int f=p1.first;
int g=min(p1.second,p2.second);
b.push_back(g+1);
if(e[{mp[{f,g}],mp[{f-2,g}]}]||e[{mp[{f,g}],mp[{f+2,g}]}])
a.push_back(f+1);
else a.push_back(f-1);
}
else
{
int f=min(p1.first,p2.first);
int g=p1.second;
a.push_back(f+1);
if(e[{mp[{f,g}],mp[{f,g-2}]}]||e[{mp[{f,g}],mp[{f,g+2}]}])
b.push_back(g-1);
else b.push_back(g+1);
}
if(bench[{a[i],b[i]}])while(1);
bench[{a[i],b[i]}]=1;
}
for(int i=0;i<k-1;i++)
v[i]--,u[i]--;
build(v,u,a,b);
return 1;
}
