#include "parks.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
map<pii,int> mp;
map<pii,int> pair_mp;
map<pii,int> is_down;
pii points[200001];
bool odw[200001];
vector<pii> graph[200001];
int n;
vector<pair<int,pii>> pairs;
vector<pii> dir = {{0,2},{0,-2},{2,0},{-2,0}};
int get(pii p)
{
if(mp.find(p) == mp.end()) return -1;
return mp[p];
}
void dfs(int v)
{
if(odw[v]) return;
odw[v] = 1;
forall(it,dir)
{
pii p = {points[v].ff+it.ff,points[v].ss+it.ss};
if(mp.find(p) != mp.end()) dfs(mp[p]);
}
}
vi ans_edge[2];
vi ans_bench[2];
void add_x1(int x, int y)
{
ans_edge[0].pb(get({x+2,y}));
ans_edge[1].pb(get({x+2,y+2}));
ans_bench[0].pb(x+1);
ans_bench[1].pb(y+1);
if(get({x,y}) != -1)
{
while(get({x,y}) != -1 && get({x+2,y}) != -1)
{
is_down[{x,y}] = 1;
y -= 2;
}
}
}
void add_x2(int x, int y)
{
ans_edge[0].pb(get({x,y}));
ans_edge[1].pb(get({x,y+2}));
ans_bench[0].pb(x+1);
ans_bench[1].pb(y+1);
if(get({x+2,y}) != -1)
{
while(get({x,y}) != -1 && get({x+2,y}) != -1)
{
is_down[{x,y}] = 1;
y -= 2;
}
}
}
int construct_roads(vi x, vi y)
{
n = siz(x);
rep(i,n)
{
mp[{x[i],y[i]}] = i;
points[i] = {x[i],y[i]};
}
dfs(0);
rep(i,n) if(!odw[i]) return 0;
rep(i,n)
{
if((get({x[i]+2,y[i]}) == -1 && get({x[i]+2,y[i]-2}) != -1 && get({x[i],y[i]-2}) != -1) || (get({x[i]+2,y[i]-2}) == -1 && get({x[i],y[i]-2}) != -1))
{
int x2 = x[i];
while(get({x2,y[i]}) != -1 && get({x2,y[i]-2}) != -1) x2-=2;
pair_mp[{x[i],y[i]-2}] = siz(pairs);
pair_mp[{x2,y[i]-2}] = siz(pairs);
pairs.pb({y[i]-2,{x2,x[i]}});
}
}
rep(i,n) odw[i] = 0;
rep(i,siz(pairs))
{
int y = pairs[i].ff;
int x1 = pairs[i].ss.ff;
int x2 = pairs[i].ss.ss;
if(get({x1,y}) != -1)
{
int y2 = y;
while(get({x1,y2}) != -1 && get({x1+2,y2}) != -1) y2-=2;
if(get({x1,y2}) == -1 && get({x1+2,y2}) == -1) rep3(y3,y2+2,y,2) is_down[{x1,y3}] = 1;
else graph[i].pb({pair_mp[{x1,y2}],x1});
}
else if(get({x1,y+2}) != -1)
{
int y2 = y+2;
while(get({x1,y2}) != -1 && get({x1+2,y2}) != -1) y2+=2;
if(!(get({x1,y2}) == -1 && get({x1+2,y2}) == -1)) graph[i].pb({pair_mp[{x1,y2-2}],x1});
}
if(get({x2+2,y}) != -1)
{
int y2 = y;
while(get({x2,y2}) != -1 && get({x2+2,y2}) != -1) y2-=2;
if(get({x2,y2}) == -1 && get({x2+2,y2}) == -1) rep3(y3,y2+2,y,2) is_down[{x2,y3}] = 1;
else graph[i].pb({pair_mp[{x2,y2}],x2});
}
else if(get({x2+2,y+2}) != -1)
{
int y2 = y+2;
while(get({x2,y2}) != -1 && get({x2+2,y2}) != -1) y2+=2;
if(!(get({x2,y2}) == -1 && get({x2+2,y2}) == -1)) graph[i].pb({pair_mp[{x2,y2-2}],x2});
}
}
rep(d,2)
{
ans_edge[d] = {};
ans_bench[d] = {};
}
rep(i,siz(pairs))
{
if(odw[i] || siz(graph[i]) == 2) continue;
odw[i] = 1;
if(siz(graph[i]) == 0)
{
ans_edge[0].pb(get({pairs[i].ss.ss,pairs[i].ff}));
ans_edge[1].pb(get({pairs[i].ss.ss,pairs[i].ff+2}));
ans_bench[0].pb(pairs[i].ss.ss+1);
ans_bench[1].pb(pairs[i].ff+1);
}
else
{
int v = i;
while(true)
{
odw[v] = 1;
pii nxt = {-1,-1};
forall(it,graph[v]) if(!odw[it.ff]) nxt = it;
if(nxt.ff == -1) break;
if(nxt.ss == pairs[v].ss.ff) add_x1(nxt.ss,pairs[v].ff);
else add_x2(nxt.ss,pairs[v].ff);
v = nxt.ff;
}
int ok_x = pairs[v].ss.ff;
forall(it,graph[v]) if(it.ss == ok_x) ok_x = pairs[v].ss.ss;
if(ok_x == pairs[v].ss.ff) add_x1(ok_x,pairs[v].ff);
else add_x2(ok_x,pairs[v].ff);
}
}
rep(i,siz(pairs))
{
if(odw[i]) continue;
int v = i;
int first_ = -1;
while(true)
{
odw[v] = 1;
pii nxt = {-1,-1};
forall(it,graph[v]) if(!odw[it.ff]) nxt = it;
if(nxt.ff == -1) break;
if(v == i) first_ = nxt.ss;
if(nxt.ss == pairs[v].ss.ff) add_x1(nxt.ss,pairs[v].ff);
else add_x2(nxt.ss,pairs[v].ff);
v = nxt.ff;
}
int ok_x = 0;
forall(it,graph[v]) if(it.ff == i && it.ss != first_) ok_x = it.ss;
if(ok_x == pairs[v].ss.ff) add_x1(ok_x,pairs[v].ff);
else add_x2(ok_x,pairs[v].ff);
}
rep(i,n)
{
if(get({x[i]+2,y[i]}) != -1)
{
ans_edge[0].pb(i);
ans_edge[1].pb(get({x[i]+2,y[i]}));
if(is_down[{x[i],y[i]}])
{
ans_bench[0].pb(x[i]+1);
ans_bench[1].pb(y[i]-1);
}
else
{
ans_bench[0].pb(x[i]+1);
ans_bench[1].pb(y[i]+1);
}
}
}
build(ans_edge[0],ans_edge[1],ans_bench[0],ans_bench[1]);
return 1;
}
