#include "parks.h"
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()
const int mxn = 2e5+10;
int N;
int S;
struct DSU{
int dsu[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
dsu[root(a)] = root(b);
}
};
DSU dsu;
vector<int> ans[4];
void addans(int s,int e,int x,int y){
dsu.onion(s,e);
ans[0].push_back(s);
ans[1].push_back(e);
ans[2].push_back(x);
ans[3].push_back(y);
return;
}
map<pii,int> mp;
vector<pii> edges;
vector<pii> all;
void check(int a,int b){
if(dsu.root(a) == dsu.root(b))return;
edges.push_back(pii(a,b));
dsu.onion(a,b);
return;
}
vector<int> lef[mxn],rig[mxn*2];
int mx[mxn],my[mxn*2];
int deg[mxn*6];
bitset<mxn> done;
void dfs(int now){
if(mx[now] != -1)return;
int tar = -1;
for(auto nxt:lef[now]){
if(my[nxt] == -1){
if(tar == -1)tar = nxt;
else if(tar != -1&°[nxt]>deg[tar])tar = nxt;
}
}
assert(tar != -1);
mx[now] = tar;
my[tar] = now;
for(auto nxt:rig[mx[now]]){
if(mx[nxt] == -1)dfs(nxt);
}
return;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
S = clock();
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
N = x.size();
for(int i = 0;i<N;i++){
pii pos = pii(x[i],y[i]);
if(mp.find(pii(pos.fs-2,pos.sc)) != mp.end())check(mp[pii(pos.fs-2,pos.sc)],i);
if(mp.find(pii(pos.fs+2,pos.sc)) != mp.end())check(mp[pii(pos.fs+2,pos.sc)],i);
if(mp.find(pii(pos.fs,pos.sc-2)) != mp.end())check(mp[pii(pos.fs,pos.sc-2)],i);
if(mp.find(pii(pos.fs,pos.sc+2)) != mp.end())check(mp[pii(pos.fs,pos.sc+2)],i);
mp[pos] = i;
}
if(edges.size() != N-1)return 0;
for(int i = 0;i<edges.size();i++){
auto [s,e] = edges[i];
if(x[s]>x[e])swap(s,e);
if(x[s] == x[e]&&y[s]>y[e])swap(s,e);
if(x[s] == x[e]){
all.push_back(pii(x[s]-1,(y[s]+y[e])>>1));
all.push_back(pii(x[s]+1,(y[s]+y[e])>>1));
}
else if(y[s] == y[e]){
all.push_back(pii((x[s]+x[e])>>1,y[s]-1));
all.push_back(pii((x[s]+x[e])>>1,y[s]+1));
}
}
//cerr<<"EDGES: ";for(auto [s,e]:edges)cerr<<s<<' '<<e<<endl;
sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());
for(int i = 0;i<edges.size();i++){
auto [s,e] = edges[i];
if(x[s] == x[e]){
int p = lower_bound(_all(all),pii(x[s]-1,(y[s]+y[e])>>1))-all.begin();
rig[p].push_back(i);
deg[p]++;
lef[i].push_back(p);
p = lower_bound(_all(all),pii(x[s]+1,(y[s]+y[e])>>1))-all.begin();
rig[p].push_back(i);
deg[p]++;
lef[i].push_back(p);
}
else if(y[s] == y[e]){
int p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]-1))-all.begin();
deg[p]++;
rig[p].push_back(i);
lef[i].push_back(p);
p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]+1))-all.begin();
rig[p].push_back(i);
deg[p]++;
lef[i].push_back(p);
}
}
queue<int> q;
for(int i = 0;i<all.size();i++){
if(deg[i] == 1)q.push(i);
}
memset(mx,-1,sizeof(mx));
memset(my,-1,sizeof(my));
while(!q.empty()){
auto now = q.front();
q.pop();
int tar = -1;
for(auto nxt:rig[now]){
if(mx[nxt] == -1)tar = nxt;
}
if(tar == -1)continue;
mx[tar] = now;
my[now] = tar;
for(auto nxt:lef[tar]){
deg[nxt]--;
if(deg[nxt] == 1)q.push(nxt);
}
}
for(int i = 0;i<all.size();i++){
if(my[i] != -1)continue;
if(deg[i] == 3){
int tar = -1;
vector<int> v;
map<int,int> mp;
for(auto &j:rig[i]){
if(mx[j] != -1)continue;
auto &[s,e]=edges[j];
mp[s]++;
mp[e]++;
if(x[s]>x[e]||(x[s] == x[e]&&y[s]>y[e]))swap(s,e);
v.push_back(j);
}
pii pos = pii(-1,-1);
for(auto &j:mp){
if(j.sc>1){
if(pos.fs == -1)pos.fs = j.fs;
else pos.sc = j.sc;
}
}
if(v.size() != 3)exit(0);
assert(v.size() == 3);
for(auto &j:v){
auto now = edges[j];
if(now.fs == pos.fs&&now.sc == pos.sc)tar = j;
else if(now.fs == pos.sc&&now.sc == pos.fs)tar = j;
}
assert(tar != -1);
mx[tar] = i;
my[i] = tar;
for(auto &j:rig[i]){
if(mx[j] == -1)dfs(j);
}
}
}
for(int i = 0;i<edges.size();i++){
if(mx[i] != -1)continue;
dfs(i);
}
for(int i = 0;i<edges.size();i++){
if(mx[i] == -1)return 0;
int tar = mx[i];
addans(edges[i].fs,edges[i].sc,all[tar].fs,all[tar].sc);
}
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
