#include "parks.h"
#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
ll x,y,id;
point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
bool operator < (const point &p)const {
return MP(x,y) < MP(p.x,p.y);
}
};
namespace sub1{
ll solve(vector <ll> x,vector <ll> y){
for (auto z:x)if (z > 6 || z < 2)return -1;
ll n = sz(x);
vector <pll> all[7];
vector <point> a(n);
for (ll i = 0;i < n;i ++){
a[i] = {x[i],y[i],i};
}
sort(a.begin(),a.end());
for (ll i = 0;i < n;i ++){
if (all[a[i].x].empty() || all[a[i].x].back().se + 2 != a[i].y)all[a[i].x].push_back(MP(a[i].y,a[i].y));
else{
all[a[i].x].back().se+=2;
}
}
vector <int> U, V, A, B;
auto add = [&](pll u,pll v, ll x,ll y){
// cout<<u.fi<<' '<<u.se<<' '<<v.fi<<' '<<v.se<<endl;
U.push_back((*lower_bound(a.begin(),a.end(),point(u.fi,u.se,0))).id);
V.push_back((*lower_bound(a.begin(),a.end(),point(v.fi,v.se,0))).id);
A.push_back(x);
B.push_back(y);
};
for (auto x:all[2]){
for (ll i = x.fi + 2;i <= x.se;i += 2){
add(MP(2,i-2),MP(2,i),1,i-1);
}
}
for (auto x:all[4]){
static ll ptr2 = 0;
static ll ptr6 = 0;
vector <ll> sus2,sus6;
while (ptr2 < sz(all[2]) && all[2][ptr2].se < x.fi)ptr2++;
while (ptr2 < sz(all[2]) && all[2][ptr2].fi <= x.se){
// cout<<all[2][ptr2].fi<<' '<<all[2][ptr2].se<<endl;
pll tmp = all[2][ptr2];
if (tmp.fi <= x.fi && x.fi <= tmp.se){
add(MP(4,x.fi),MP(2,x.fi),3,x.fi-1);
}
else if (tmp.fi <= x.se && x.se <= tmp.se){
add(MP(4,x.se),MP(2,x.se),3,x.se+1);
}
else{
sus2.push_back(tmp.fi);
}
ptr2++;
}
while (ptr6 < sz(all[6]) && all[6][ptr6].se < x.fi)ptr6++;
while (ptr6 < sz(all[6]) && all[6][ptr6].fi <= x.se){
pll tmp = all[6][ptr6];
if (tmp.fi <= x.fi && x.fi <= tmp.se){
add(MP(4,x.fi),MP(6,x.fi),5,x.fi-1);
}
else if (tmp.fi <= x.se && x.se <= tmp.se){
add(MP(4,x.se),MP(6,x.se),5,x.se+1);
}
else{
sus6.push_back(tmp.fi);
}
ptr6++;
}
ptr2=0,ptr6=0;
for (ll j = x.fi + 2;j <= x.se;j += 2){
while(ptr2 < sz(sus2) && sus2[ptr2]<j)ptr2++;
while(ptr6 < sz(sus6) && sus6[ptr6]<j)ptr6++;
bool do2,do6;
do2 = (ptr2 < sz(sus2) && sus2[ptr2]==j);
do6 = (ptr6 < sz(sus6) && sus6[ptr6]==j);
if (do2 && do6){
add(MP(4,j),MP(2,j),3,j-1);
add(MP(4,j),MP(6,j),5,j+1);
add(MP(4,j),MP(4,j-2),5,j-1);
add(MP(4,j),MP(4,j+2),3,j+1);
j+=2;
}
else if (do2){
add(MP(4,j),MP(2,j),3,j-1);
add(MP(4,j),MP(4,j-2),5,j-1);
}
else if (do6){
add(MP(4,j),MP(6,j),5,j-1);
add(MP(4,j),MP(4,j-2),3,j-1);
}
else add(MP(4,j),MP(4,j-2),3,j-1);
}
}
for (auto x:all[6]){
for (ll i = x.fi + 2;i <= x.se;i += 2){
add(MP(6,i-2),MP(6,i),7,i-1);
}
}
{
vector <vector <ll > > g(n);
for (ll i = 0;i < sz(U);i ++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
vector <bool> in(n);
queue <ll> q;
q.push(0);
in[0] = 1;
while (!q.empty()){
ll u = q.front();
q.pop();
for (auto v:g[u]){
if (!in[v]){
in[v] = 1;
q.push(v);
}
}
}
for (ll i = 0;i < n;i ++)if (!in[i])return 0;
build(U, V, A, B);
return 1;
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll tmp = sub1::solve(x,y);
if (tmp != -1)return tmp;
ll n = sz(x);
vector <point> a(n);
for (ll i = 0;i < n;i ++){
a[i] = {x[i],y[i],i};
}
sort(a.begin(),a.end());
vector <int> U, V, A, B;
auto add = [&](pll u,pll v, ll x,ll y){
// cout<<u.fi<<' '<<u.se<<' '<<v.fi<<' '<<v.se<<endl;
U.push_back((*lower_bound(a.begin(),a.end(),point(u.fi,u.se,0))).id);
V.push_back((*lower_bound(a.begin(),a.end(),point(v.fi,v.se,0))).id);
A.push_back(x);
B.push_back(y);
};
vector <pll> last;
// for (ll i = 0;i < n;i ++)cout<<a[i].x<<' '<<a[i].y<<'\n';
for (ll i = 0;i < n;i ++){
// cout<<a[i].x<<' '<<a[i-1].x<<' '<<i<<endl;
if (i && a[i].x != a[i-1].x+2)return 0;
ll j = i;
while (j < n && a[j].x==a[i].x)j++;
j--;
vector <pll> all;
for (ll k = i;k <= j;k ++){
if (all.empty() || all.back().se + 2 != a[k].y)all.push_back(MP(a[k].y,a[k].y));
else{
all.back().se+=2;
}
}
ll ptr = 0;
for (auto x:all){
while (ptr < sz(last) && last[ptr].se < x.fi)ptr++;
while (ptr < sz(last) && last[ptr].fi <= x.se){
pll tmp = last[ptr];
if (tmp.fi <= x.fi && x.fi <= tmp.se){
add(MP(a[i].x,x.fi),MP(a[i].x-2,x.fi),a[i].x-1,x.fi-1);
}
else if (tmp.fi <= x.se && x.se <= tmp.se){
add(MP(a[i].x,x.se),MP(a[i].x-2,x.se),a[i].x-1,x.se+1);
}
ptr++;
}
for (ll k = x.fi + 2;k <= x.se;k += 2){
add(MP(a[i].x,k),MP(a[i].x,k-2),a[i].x-1,k-1);
}
}
last = all;
i=j;
}
{
vector <vector <ll > > g(n);
for (ll i = 0;i < sz(U);i ++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
vector <bool> in(n);
queue <ll> q;
q.push(0);
in[0] = 1;
while (!q.empty()){
ll u = q.front();
q.pop();
for (auto v:g[u]){
if (!in[v]){
in[v] = 1;
q.push(v);
}
}
}
for (ll i = 0;i < n;i ++)if (!in[i])return 0;
build(U, V, A, B);
return 1;
}
}
