#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int MXN = 2e5+5;
namespace two_sat {
int n, cmp[MXN<<1];
bool vis[MXN<<1];
vector<int> g[MXN<<1], gr[MXN<<1], ord;
inline void add_edge(int u, int v) {
g[u].push_back(v);
gr[v].push_back(u);
}
inline void add(int u, bool nu, int v, bool nv) {
add_edge(2*u+1-nu, 2*v+nv);
add_edge(2*v+1-nv, 2*u+nu);
}
void dfs(int v) {
vis[v] = 1;
for(int u : g[v])
if(!vis[u])
dfs(u);
ord.push_back(v);
}
void dfsr(int v, int c) {
cmp[v] = c;
for(int u : gr[v])
if(!cmp[u])
dfsr(u, c);
}
bool solve(vector<bool> &ans) {
for(int i=0; i<2*n; i++)
if(!vis[i])
dfs(i);
int c=0;
while(!ord.empty()) {
int v = ord.back();
ord.pop_back();
if(!cmp[v]) dfsr(v, ++c);
}
for(int i=0; i<n; i++)
if(cmp[2*i]==cmp[2*i+1]) return 0;
else ans[i] = (cmp[2*i+1]>cmp[2*i]);
return 1;
}
}
int n, ord[MXN], dsu[MXN];
pii P[MXN];
int find(int v) { return v==dsu[v] ? v : dsu[v] = find(dsu[v]); };
inline void merge(int u, int v) { dsu[find(v)] = find(u); }
inline int id(pii p) {
int pos = lower_bound(P, P+n, p)-P;
return pos<n && P[pos]==p ? ord[pos] : -1;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
iota(ord, ord+n, 0);
sort(ord, ord+n, [&](int i, int j) {
return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]);
});
for(int i=0; i<n; i++) P[i] = pii(x[ord[i]], y[ord[i]]);
iota(dsu, dsu+n, 0);
vector<int> U, V;
vector<int> ord2(n);
iota(ord2.begin(), ord2.end(), 0);
sort(ord2.begin(), ord2.end(), [&](int i, int j) {
return x[i]+y[i]<x[j]+y[j] || (x[i]+y[i]==x[j]+y[j] && x[i]<x[j]);
});
for(int i,t=0; t<n; t++) {
i = ord2[t];
int j = id(pii(x[i], y[i]-2));
if(j!=-1 && find(i)!=find(j)) {
U.push_back(i);
V.push_back(j);
merge(i, j);
}
j = id(pii(x[i]-2, y[i]));
if(j!=-1 && find(i)!=find(j)) {
U.push_back(i);
V.push_back(j);
merge(i, j);
}
}
if(U.size()!=n-1) return 0;
two_sat::n = n-1;
map<pii, vector<pair<int, bool>>> mp;
for(int i=0; i<n-1; i++)
if(x[U[i]]==x[V[i]])
mp[{x[U[i]]-1, (y[U[i]]+y[V[i]])>>1}].push_back({i, 0}),
mp[{x[U[i]]+1, (y[U[i]]+y[V[i]])>>1}].push_back({i, 1});
else
mp[{(x[U[i]]+x[V[i]])>>1, y[U[i]]-1}].push_back({i, 0}),
mp[{(x[U[i]]+x[V[i]])>>1, y[U[i]]+1}].push_back({i, 1});
for(auto tmp : mp)
for(int i=0; i<tmp.Y.size(); i++)
for(int j=0; j<tmp.Y.size(); j++)
if(i^j)
two_sat::add(tmp.Y[i].X, tmp.Y[i].Y^1, tmp.Y[j].X, tmp.Y[j].Y^1);
vector<bool> ans(n-1);
if(!two_sat::solve(ans)) return 0;
vector<int> A(n-1), B(n-1);
for(int i=0; i<n-1; i++)
if(x[U[i]]==x[V[i]]) {
if(ans[i]) A[i] = x[U[i]]+1, B[i] = (y[U[i]]+y[V[i]])>>1;
else A[i] = x[U[i]]-1, B[i] = (y[U[i]]+y[V[i]])>>1;
}
else {
if(ans[i]) A[i] = (x[U[i]]+x[V[i]])>>1, B[i] = y[U[i]]+1;
else A[i] = (x[U[i]]+x[V[i]])>>1, B[i] = y[U[i]]-1;
}
build(U, V, A, B);
return 1;
}
