#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<<endl;
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
vector<pii> adj(pii x){
int a = x.first; int b = x.second;
return {mp(a+2, b), mp(a-2, b), mp(a, b+2), mp(a, b-2)};
}
const int mxn = 2e5 + 5;
vi sz(mxn), par(mxn);
int find(int x){
while(x != par[x])x = par[x];
return x;
}
int ccs;
void unite(int a, int b){
a = find(a); b = find(b);
if(a == b)return;
ccs--;
if(sz[a] < sz[b])swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
// vector<vector<int>>grid(2, vi(mxn, -1));
vi u,v,a,b;
int n = x.size();
vector<vector<int>>grid(3, vi(mxn, -1));
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;
if(grid[0][fi] != -1 && grid[1][fi] != -1){
u.pb(grid[0][fi]); v.pb(grid[1][fi]);
}
if(grid[1][fi] != -1 && grid[2][fi] != -1){
u.pb(grid[1][fi]); v.pb(grid[2][fi]);
}
done += (grid[0][fi] != -1) + (grid[1][fi] != -1) + (grid[2][fi] != -1);
bool ok = 1;
FOR(i, fi + 1, mxn){
if(done == n)break;
if(grid[0][i] == -1 && grid[1][i] == -1 && grid[2][i] == -1){
ok = 0;
break;
}
vb vis(3);
f0r(j,3){
if(grid[j][i] == -1)vis[j] = 1;
}
if(grid[0][i] != -1 && grid[0][i-1] != -1){
u.pb(grid[0][i]);v.pb(grid[0][i-1]); vis[0] = 1;
}
if(grid[1][i] != -1 && grid[1][i-1] != -1){
u.pb(grid[1][i]); v.pb(grid[1][i-1]); vis[1] = 1;
}
if(grid[2][i] != -1 && grid[2][i-1] != -1){
u.pb(grid[2][i]); v.pb(grid[2][i-1]); vis[2] = 1;
}
if(!vis[1]){
if(vis[0]){
u.pb(grid[0][i]); v.pb(grid[1][i]); vis[1] = 1;
}
else if(vis[2]){
u.pb(grid[2][i]); v.pb(grid[1][i]); vis[1] = 1;
}
else{
ok = 0; break;
}
}
if(!vis[0]){
if(!vis[1] || grid[1][i] == -1){
ok = 0; break;
}
else{
u.pb(grid[0][i]); v.pb(grid[1][i]); vis[0] = 1;
}
}
if(!vis[2]){
if(!vis[1] || grid[1][i] == -1){
ok = 0; break;
}
else{
u.pb(grid[1][i]); v.pb(grid[2][i]); vis[2] = 1;
}
}
done += (grid[0][i] != -1) + (grid[1][i] != -1) + (grid[2][i] != -1);
}
if(!ok)return 0;
map<pii,int>m;
ccs = n;
f0r(i,n){
m[mp(x[i], y[i])] = i;
par[i] = i;
sz[i] = 1;
}
map<pii,vi>fight;
map<pii,int>fc;
/*
f0r(i,n){
for(auto s : adj(mp(x[i], y[i]))){
if(m.count(s) && m[s] > i){
if(find(i) != find(m[s])){
u.pb(i); v.pb(m[s]);
unite(i, m[s]);
int x1 = x[i]; int y1 = y[i]; int x2 = x[m[s]]; int y2 = y[m[s]];
if(x1 == x2){
fight[mp(x1 + 1, (y1 + y2) / 2)].pb(u.size() - 1);
fight[mp(x1 - 1, (y1 + y2) / 2)].pb(u.size() - 1);
}
else{
fight[mp((x1 + x2) / 2, y1 + 1)].pb(u.size() - 1);
fight[mp((x1 + x2) / 2, y1 - 1)].pb(u.size() - 1);
}
}
}
}
}
*/
f0r(i, u.size()){
int x1 = x[u[i]]; int y1 = y[u[i]]; int x2 = x[v[i]]; int y2 = y[v[i]];
unite(u[i], v[i]);
if(x1 == x2){
fight[mp(x1 + 1, (y1 + y2) / 2)].pb(i);
fight[mp(x1 - 1, (y1 + y2) / 2)].pb(i);
}
else{
fight[mp((x1 + x2) / 2, y1 + 1)].pb(i);
fight[mp((x1 + x2) / 2, y1 - 1)].pb(i);
}
}
if(ccs > 1)return 0;
int visd = 0;
queue<pii>q; //stores benches
vb vis(u.size());
a.resize(u.size()); b.resize(u.size());
set<pii>twos;
for(auto u : fight){
// vout(u.second);
fc[u.first] = u.second.size();
if(fc[u.first] == 1){
q.push(u.first);
}
if(fc[u.first] == 2){
twos.insert(u.first);
}
}
int iter = 0;
while(visd < u.size()){
if(q.empty()){
q.push(*twos.begin());
}
while(!q.empty()){
pii node = q.front(); q.pop();
fc[node] = 0; twos.erase(node);
// cout<<node.first<<' '<<node.second<<'\n';
for(auto cur : fight[node]){
if(!vis[cur]){
a[cur] = node.first; b[cur] = node.second; vis[cur] = 1; visd++;
int x1 = x[u[cur]]; int x2 = x[v[cur]]; int y1 = y[u[cur]]; int y2 = y[v[cur]];
if(x1 == x2){
if(fc.count(mp(x1 + 1, (y1 + y2) / 2))){
int thing = --fc[mp(x1 + 1, (y1 + y2) / 2)];
if(thing == 1){
q.push(mp(x1 + 1, (y1 + y2) / 2));
twos.erase(mp(x1 + 1, (y1 + y2) / 2));
}
else if(thing == 2){
twos.insert(mp(x1 + 1, (y1 + y2) / 2));
}
}
if(fc.count(mp(x1 - 1, (y1 + y2) / 2))){
int thing = --fc[mp(x1 - 1, (y1 + y2) / 2)];
if(thing == 1){
q.push(mp(x1 - 1, (y1 + y2) / 2));
twos.erase(mp(x1 - 1, (y1 + y2) / 2));
}
else if(thing == 2){
twos.insert(mp(x1 - 1, (y1 + y2) / 2));
}
}
}
else{
if(fc.count(mp((x1 + x2) / 2, y1 + 1))){
int thing = --fc[mp((x1 + x2) / 2, y1 + 1)];
if(thing == 1){
q.push(mp((x1 + x2) / 2, y1 + 1));
twos.erase(mp((x1 + x2) / 2, y1 + 1));
}
else if(thing == 2){
twos.insert(mp((x1 + x2) / 2, y1 + 1));
}
}
if(fc.count(mp((x1 + x2) / 2, y1 - 1))){
int thing = --fc[mp((x1 + x2) / 2, y1 - 1)];
if(thing == 1){
q.push(mp((x1 + x2) / 2, y1 - 1));
twos.erase(mp((x1 + x2) / 2, y1 - 1));
}
else if(thing == 2){
twos.insert(mp((x1 + x2) / 2, y1 - 1));
}
}
}
break;
}
}
}
}
/*
bool ok = 1;
f0r(i, u.size()){
if(!vis[i])ok= 0;
}
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;
*/
}
