#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
void build(vector<int>,vector<int>,vector<int>,vector<int>);
int X[200005];
int Y[200005];
typedef pair<int,int> P;
int N;
map<P,int> M;
vector<vector<int>> adj;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct UnionFind {
vector<int> root;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
}
int Find(int n) {
if(root[n]<0) return n;
int r = Find(root[n]);
root[n] = r;
return r;
}
void Merge(int x, int y) {
x = Find(x), y = Find(y);
if(x==y) return;
if(root[x]>root[y]) swap(x, y);
root[x] += root[y];
root[y] = x;
}
};
vector<P> Edge;
const int INF = 1e8;
int dm[2] = {1,-1};
int construct_roads(vector<int> _X, vector<int> _Y) {
N = _X.size();
int i, j;
for(i=0;i<N;i++) {
X[i] = _X[i];
Y[i] = _Y[i];
M[P(X[i],Y[i])] = i;
}
adj.resize(N);
for(i=0;i<N;i++) {
for(j=0;j<4;j++) {
int x = X[i] + 2*dx[j];
int y = Y[i] + 2*dy[j];
if(M.count(P(x,y))) {
int id = M[P(x,y)];
adj[id].push_back(i);
adj[i].push_back(id);
Edge.push_back(P(i,id));
}
}
}
vector<P> Tree;
UnionFind UF(N);
for(i=0;i<Edge.size();i++) {
if(UF.Find(Edge[i].first) != UF.Find(Edge[i].second)) {
Tree.push_back(Edge[i]);
UF.Merge(Edge[i].first, Edge[i].second);
}
}
for(i=0;i<N;i++) {
if(UF.Find(0)!=UF.Find(i)) return 0;
}
vector<int> A, B;
for(i=0;i<Tree.size();i++) {
int x1 = X[Tree[i].first];
int y1 = Y[Tree[i].first];
int x2 = X[Tree[i].second];
int y2 = Y[Tree[i].second];
//cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << '\n';
if(x1==x2) {
int x = x1;
int y = (y1+y2)/2;
for(j=0;j<1;j++) {
int x3 = x + dm[j];
if(true) {
A.push_back(x3);
B.push_back(y);
//cout << "push1\n";
}
}
}
if(y1==y2) {
int x = (x1+x2)/2;
int y = y2;
for(j=0;j<2;j++) {
int y3 = y + dm[j];
if(1==y3%4) {
A.push_back(x);
B.push_back(y3);
//cout << "push2\n";
}
}
}
}
vector<int> U, V;
for(i=0;i<Tree.size();i++) {
U.push_back(Tree[i].first);
V.push_back(Tree[i].second);
}
/*for(i=0;i<U.size();i++) cout <<U[i] << ' ';
cout << '\n';
for(i=0;i<V.size();i++) cout << V[i] << ' ';
cout << '\n';
for(i=0;i<A.size();i++)cout <<A[i] << ' ';
cout << '\n';
for(i=0;i<B.size();i++) cout << B[i] <<' ';
cout << '\n';*/
build(U, V, A, B);
return 1;
}
