#include "parks.h"
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
int N;
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;
struct DINIC{
struct E{
int t,f,c;
E(int tt = 0,int cc = 0,int ff = 0):t(tt),c(cc),f(ff){}
};
vector<int> lvl,ptr;
vector<vector<int>> paths;
vector<E> e;
DINIC(int n = 0){
lvl = vector<int>(n,0);
ptr = vector<int>(n,0);
paths.resize(n);
e.clear();
}
void add_edge(int a,int b,int c,int d = 0){
paths[a].push_back(e.size());
e.push_back(E(b,c,0));
paths[b].push_back(e.size());
e.push_back(E(a,d,0));
return;
}
queue<int> q;
bool bfs(int s,int t){
fill(lvl.begin(),lvl.end(),-1);
fill(ptr.begin(),ptr.end(),0);
lvl[s] = 0;
q.push(s);
while(!q.empty()){
auto now = q.front();
q.pop();
for(int i = 0;i<paths[now].size();i++){
int eid = paths[now][i];
if(e[eid].f == e[eid].c||lvl[e[eid].t] != -1)continue;
lvl[e[eid].t] = lvl[now]+1;
q.push(e[eid].t);
}
}
return lvl[t] != -1;
}
int dfs(int now,int t,int fl){
if(now == t)return fl;
for(int &i = ptr[now];i<paths[now].size();i++){
int eid = paths[now][i];
if(e[eid].f == e[eid].c)continue;
int nxt = e[eid].t;
int re = 0;
if(re = dfs(nxt,t,min(fl,e[eid].c-e[eid].f))){
e[eid].f += re;
e[eid^1].f -= re;
return re;
}
}
return 0;
}
int flow(int s,int t){
int ans = 0;
while(bfs(s,t)){
int re = 0;
while(re = dfs(s,t,INT_MAX))ans += re;
}
return ans;
}
};
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;
DINIC g;
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;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
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));
}
}
assert(all.size()<1e6);
//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());
g = DINIC(all.size()+edges.size()+2);
int s = all.size()+edges.size();int t = s+1;
for(int i = 0;i<edges.size();i++){
g.add_edge(s,i,1);
}
for(int i = 0;i<all.size();i++){
g.add_edge(edges.size()+i,t,1);
}
for(int i = 0;i<edges.size();i++){
auto [s,e] = edges[i];
if(x[s] == x[e]){
int p = lower_bound(all.begin(),all.end(),pii(x[s]-1,(y[s]+y[e])>>1))-all.begin();
g.add_edge(i,p+edges.size(),1);
p = lower_bound(all.begin(),all.end(),pii(x[s]+1,(y[s]+y[e])>>1))-all.begin();
g.add_edge(i,p+edges.size(),1);
}
else if(y[s] == y[e]){
int p = lower_bound(all.begin(),all.end(),pii((x[s]+x[e])>>1,y[s]-1))-all.begin();
g.add_edge(i,p+edges.size(),1);
p = lower_bound(all.begin(),all.end(),pii((x[s]+x[e])>>1,y[s]+1))-all.begin();
g.add_edge(i,p+edges.size(),1);
}
}
int st = clock();
int re = 0;
while(clock()-st<0.5*CLOCKS_PER_SEC){
re = rand();
}
re = g.flow(s,t);
if(re != N-1)return 0;
for(int i = 0;i<edges.size();i++){
for(int j = 0;j<g.paths[i].size();j++){
int eid = g.paths[i][j];
int nxt = g.e[eid].t;
if(g.e[eid].f == 1){
addans(edges[i].fs,edges[i].sc,all[nxt-edges.size()].fs,all[nxt-edges.size()].sc);
}
}
}
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
