#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point{
int x, y, n;
point(){}
point(int _x, int _y, int _n): x(_x), y(_y), n(_n) {}
bool operator<(const point &P) const{
if (x+y==P.x+P.y) return y<P.y;
return x+y<P.x+P.y;
}
};
struct DSU{
int path[200200];
void init(int n){
for (int i=0;i<n;i++) path[i] = i;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
void merge(int s, int v){
int x = find(s), y = find(v);
if (x==y) return;
path[x] = y;
}
}dsu;
struct Vertex{
int s, e, x, y;
Vertex(){}
Vertex(int _s, int _e, int _x, int _y): s(_s), e(_e), x(_x), y(_y) {}
};
map<int, int> mp[200200];
multimap<pair<int, int>, int> INV;
vector<Vertex> graph;
vector<int> adj[400400], inv[400400];
bool make_edge(int x, int y, int x2, int y2){
if (mp[x].find(y)==mp[x].end() || mp[x2].find(y2)==mp[x2].end()) return 0;
int tmp1 = mp[x][y], tmp2 = mp[x2][y2];
if (dsu.find(tmp1)==dsu.find(tmp2)) return 0;
if (tmp1>tmp2) swap(tmp1, tmp2);
dsu.merge(tmp1, tmp2);
if (x==x2){
graph.emplace_back(tmp1, tmp2, x-1, (y+y2)/2);
graph.emplace_back(tmp1, tmp2, x+1, (y+y2)/2);
INV.insert(make_pair(make_pair(x-1, (y+y2)/2), (int)graph.size()-2));
INV.insert(make_pair(make_pair(x+1, (y+y2)/2), (int)graph.size()-1));
}
else{
graph.emplace_back(tmp1, tmp2, (x+x2)/2, y-1);
graph.emplace_back(tmp1, tmp2, (x+x2)/2, y+1);
INV.insert(make_pair(make_pair((x+x2)/2, y-1), (int)graph.size()-2));
INV.insert(make_pair(make_pair((x+x2)/2, y+1), (int)graph.size()-1));
}
return 1;
}
bool valid(int n){
bool ret = 1;
for (int i=0;i<n-1;i++) if (dsu.find(i)!=dsu.find(i+1)) ret = 0;
return ret;
}
int sccnum[400400], col[400400], cnt = 0;
bool visited[400400];
stack<int> st;
vector<vector<int>> scc;
void dfs1(int s){
visited[s] = 1;
for (auto &v:adj[s]) if (!visited[v]) dfs1(v);
st.push(s);
}
void dfs2(int s){
visited[s] = 1;
sccnum[s] = cnt;
scc.back().push_back(s);
for (auto &v:inv[s]) if (!visited[v]) dfs2(v);
}
void getscc(int n){
for (int i=0;i<n;i++){
for (auto &v:adj[i]) inv[v].push_back(i);
}
for (int i=0;i<n;i++) if (!visited[i]) dfs1(i);
fill(visited, visited+n, 0);
scc.push_back(vector<int>());
while(!st.empty()){
int cur = st.top(); st.pop();
if (visited[cur]) continue;
cnt++;
scc.push_back(vector<int>());
dfs2(cur);
}
}
bool cmp(point &x, point &y){
if (x.y==y.y) return x.x<y.x;
return x.y<y.y;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
std::vector<int> ansu, ansv, ansa, ansb;
vector<point> vec;
int n = x.size();
for (int i=0;i<n;i++){
vec.emplace_back(x[i], y[i], i);
mp[x[i]][y[i]] = i;
}
///graph modeling
dsu.init(n);
sort(vec.begin(), vec.end());
for (int i=0;i<n;i++) if ((vec[i].x+vec[i].y)%4==2){
make_edge(vec[i].x, vec[i].y, vec[i].x+2, vec[i].y);
make_edge(vec[i].x, vec[i].y, vec[i].x, vec[i].y+2);
}
for (int i=0;i<n;i++) if ((vec[i].x+vec[i].y)%4==0){
make_edge(vec[i].x, vec[i].y, vec[i].x+2, vec[i].y);
make_edge(vec[i].x, vec[i].y, vec[i].x, vec[i].y+2);
}
if (!valid(n)) return 0;
for (auto iter=INV.begin();iter!=INV.end();++iter){
auto tmp = INV.equal_range(iter->first);
auto iter1 = tmp.first, iter2 = tmp.second;
for(;iter1!=iter2;++iter1){
if (iter1==iter) continue;
adj[iter->second].push_back((iter1->second)^1);
}
}
///
getscc((int)graph.size());
for (int i=0;i<(int)graph.size();i++) if (sccnum[i]==sccnum[i^1]) return 0;
///finding solution
fill(col, col+(int)graph.size(), -1);
for (auto &V:scc){
int tmp = 0;
for (auto &x:V) if (col[x]==1) tmp = 1;
for (auto &x:V) col[x] = tmp, col[x^1] = tmp^1;
}
///
for (int i=0;i<(int)graph.size();i++) if (col[i]==1){
ansu.push_back(graph[i].s);
ansv.push_back(graph[i].e);
ansa.push_back(graph[i].x);
ansb.push_back(graph[i].y);
}
build(ansu, ansv, ansa, ansb);
return 1;
}
