#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 800007
using namespace std;
struct bench{
int from,to;
int a,b;
};
int n,curr,benches,br,k,comp[MAXN],ans[MAXN],dsu[MAXN],w[MAXN],sz[MAXN];
bool li[MAXN];
vector<int> v[MAXN],r[MAXN];
stack<int> st;
vector<bench> sol;
vector<int> A,B,C,D;
vector< pair<int,int> > ors;
unordered_map<long long, int> mp;
unordered_map<long long, vector<int> > bro;
int op(int x){
if(x<400000)return x+400000;
return x-400000;
}
void add(long long x,long long y,int z){
for(int i=0;i<bro[x*300000+y].size();i++){
ors.push_back({op(bro[x*300000+y][i]),op(z)});
}
bro[x*300000+y].push_back(z);
}
void dfs(int x){
li[x]=true;
for(int i=0;i<v[x].size();i++){
if(!li[v[x][i]])dfs(v[x][i]);
}
st.push(x);
}
void scc(int x){
comp[x]=k;
li[x]=true;
for(int i=0;i<r[x].size();i++){
if(!li[r[x][i]])scc(r[x][i]);
}
}
int root(int x){
if(dsu[x]==x)return x;
dsu[x]=root(dsu[x]);
return dsu[x];
}
void mergev(int x,int y){
if(sz[root(x)]<sz[root(y)])swap(x,y);
sz[root(x)]+=sz[root(y)];
dsu[root(y)]=root(x);
}
vector<long long> x,y;
void dfss(long long x,long long y){
int ss=mp[x*300000+y]-1;
curr=mp[(x-2)*300000+y];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
add(x-1,y-1,br);
add(x-1,y+1,br+1);
ors.push_back({br,br+1});
br+=2;
dfss(x-2,y);
}
curr=mp[(x+2)*300000+y];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
add(x+1,y-1,br);
add(x+1,y+1,br+1);
ors.push_back({br,br+1});
br+=2;
dfss(x+2,y);
}
curr=mp[x*300000+y-2];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
add(x-1,y-1,br);
add(x+1,y-1,br+1);
ors.push_back({br,br+1});
br+=2;
dfss(x,y-2);
}
curr=mp[x*300000+y+2];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
add(x-1,y+1,br);
add(x+1,y+1,br+1);
ors.push_back({br,br+1});
br+=2;
dfss(x,y+2);
}
}
void dfss2(long long x,long long y){
int ss=mp[x*300000+y]-1;
curr=mp[(x-2)*300000+y];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
if(ans[br]==1){
sol.push_back({curr,ss,x-1,y-1});
}else{
sol.push_back({curr,ss,x-1,y+1});
}
br+=2;
dfss2(x-2,y);
}
curr=mp[(x+2)*300000+y];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
if(ans[br]==1){
sol.push_back({curr,ss,x+1,y-1});
}else{
sol.push_back({curr,ss,x+1,y+1});
}
br+=2;
dfss2(x+2,y);
}
curr=mp[x*300000+y-2];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
if(ans[br]==1){
sol.push_back({curr,ss,x-1,y-1});
}else{
sol.push_back({curr,ss,x+1,y-1});
}
br+=2;
dfss2(x,y-2);
}
curr=mp[x*300000+y+2];
if(curr!=0 and root(ss)!=root(curr-1)){
curr--; mergev(ss,curr);
if(ans[br]==1){
sol.push_back({curr,ss,x-1,y+1});
}else{
sol.push_back({curr,ss,x+1,y+1});
}
br+=2;
dfss2(x,y+2);
}
}
int construct_roads(vector<int> X,vector<int> Y){
n=int(X.size());
x.resize(n); y.resize(n);
for(int i=0;i<n;i++){
dsu[i]=i; sz[i]=1;
x[i]=X[i]; y[i]=Y[i];
mp[x[i]*300000+y[i]]=i+1;
}
br=0;
dfss(x[0],y[0]);
if(br!=2*n-2)return 0;
for(int i=0;i<ors.size();i++){
v[op(ors[i].first)].push_back(ors[i].second);
r[ors[i].second].push_back(op(ors[i].first));
v[op(ors[i].second)].push_back(ors[i].first);
r[ors[i].first].push_back(op(ors[i].second));
}
for(int i=0;i<800000;i++){
if(!li[i])dfs(i);
}
for(int i=0;i<800000;i++)li[i]=false;
while(!st.empty()){
if(!li[st.top()]){
k++; scc(st.top());
}
st.pop();
}
for(int i=0;i<br;i++){
if(comp[i]==comp[op(i)])return 0;
if(comp[i]<comp[op(i)])ans[i]=0;
else ans[i]=1;
}
for(int i=0;i<n;i++){
dsu[i]=i; sz[i]=1;
}
br=0;
dfss2(x[0],y[0]);
for(int i=0;i<sol.size();i++){
A.push_back(sol[i].from);
B.push_back(sol[i].to);
C.push_back(sol[i].a);
D.push_back(sol[i].b);
}
build(A,B,C,D);
return 1;
}
/*
int main(){
cout<<construct_roads({2,2,2,2,4,4,4,4,6,6,6,6,8,8,8,8}, {2,4,6,8,2,4,6,8,2,4,6,8,2,4,6,8});
}
*/
