#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1e5+5;
struct fount
{
int x,y,i;
fount() {}
fount(int _x,int _y,int _i)
{
x=_x;
y=_y;
i=_i;
}
};
bool cmp(fount f1,fount f2)
{
return f1.y<f2.y;
}
int c;
fount p[maxn];
map<pair<int,int>,int> mp,mp1;
vector<int> u,v,a,b;
int used[maxn],in;
void dfs(int i,int pr)
{
//cout<<i<<" "<<pr<<endl;
if(pr!=-1)
{
v.push_back(i-1);
u.push_back(pr-1);
mp1[ {i,pr}]=1;
mp1[ {pr,i}]=1;
}
in++;
int cnt=0;
used[i]=1;
pair<int,int> h= {p[i].x,p[i].y};
h.first+=2;
if(mp[h]&&!used[mp[h]])
{
cnt++;
dfs(mp[h],i);
}
h.first-=4;
if(mp[h]&&!used[mp[h]])
{
cnt++;
dfs(mp[h],i);
}
h.first+=2;
h.second+=2;
if(mp[h]&&!used[mp[h]])
{
cnt++;
dfs(mp[h],i);
}
h.second-=4;
if(mp[h]&&!used[mp[h]])
{
cnt++;
dfs(mp[h],i);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y)
{
c=x.size();
for(int i=0; i<x.size(); i++)
{
p[i+1]= {x[i],y[i],i};
mp[ {x[i],y[i]}]=i+1;
}
dfs(1,-1);
if(in!=x.size())return 0;
for(int i=0; i<x.size()-1; i++)
{
if(p[v[i]+1].x==p[u[i]+1].x)
{
int x=p[v[i]+1].x;
int y=min(p[v[i]+1].y,p[u[i]+1].y);
if(mp[ {x-2,y}]/*&&mp1[ {mp[{x,y}],mp[{x-2,y}]}]*/||mp[ {x+2,y}]/*&&mp1[ {mp[{x,y}],mp[{x+2,y}]}]*/)
{
a.push_back(x-1);
b.push_back(y+1);
}
else
{
a.push_back(x+1);
b.push_back(y+1);
}
}
else
{
int x=min(p[v[i]+1].x,p[u[i]+1].x);
int y=p[v[i]+1].y;
if(mp[ {x,y-2}]/*&&mp1[ {mp[{x,y}],mp[{x,y-2}]}]*/||mp[ {x,y+2}]/*&&mp1[ {mp[{x,y}],mp[{x,y+2}]}]*/)
{
a.push_back(x+1);
b.push_back(y+1);
}
else
{
a.push_back(x+1);
b.push_back(y-1);
}
}
}
build(v,u,a,b);
return 1;
}
