#include "parks.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vvi vector<vi>
using namespace std;
const int mxn = 1e5 +5;
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<vector<int>>grid(2, vi(mxn, -1));
int n = x.size();
f0r(i,n){
int a = x[i] / 2 - 1;
int b = y[i] / 2 - 1;
grid[a][b] = i;
}
int fi = -1;
f0r(i, mxn){
if(grid[0][i] != -1 || grid[1][i] != -1){
fi = i; break;
}
}
int done = 0;
vi u,v,a,b;
if(grid[0][fi] != -1 && grid[1][fi] != -1){
u.pb(grid[0][fi]); v.pb(grid[1][fi]); a.pb(3); b.pb(fi * 2 + 1);
}
done += (grid[0][fi] != -1) + (grid[1][fi] != -1);
bool ok = 1;
FOR(i, fi + 1, mxn){
if(done == n)break;
if(grid[0][i] == -1 && grid[1][i] == -1){
ok = 0;
break;
}
if(grid[0][i] == -1 && grid[1][i] != -1 && grid[0][i-1] != -1 && grid[1][i-1] == -1){
ok = 0; break;
}
if(grid[0][i] != -1 && grid[1][i] == -1 && grid[0][i-1] == -1 && grid[1][i-1] != -1){
ok = 0; break;
}
if(grid[0][i] != -1 && grid[0][i-1] != -1){
u.pb(grid[0][i]);v.pb(grid[0][i-1]);a.pb(1);b.pb(i * 2 + 1);
}
if(grid[1][i] != -1 && grid[1][i-1] != -1){
u.pb(grid[1][i]); v.pb(grid[1][i-1]); a.pb(5); b.pb(i * 2 + 1);
}
int lef = (grid[0][i-1] != -1) + (grid[1][i-1] != -1);
int rig = (grid[0][i] != -1) + (grid[1][i] != -1);
if(lef == 1 && rig == 2){
u.pb(grid[0][i]); v.pb(grid[1][i]); a.pb(3); b.pb(i * 2 + 1);
}
done += (grid[0][i] != -1) + (grid[1][i] != -1);
}
if(!ok)return 0;
build(u,v,a,b);
return 1;
/*
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
std::vector<int> u, v, a, b;
u.push_back(0);
v.push_back(1);
a.push_back(x[0]+1);
b.push_back(y[0]-1);
build(u, v, a, b);
return 1;
*/
}
