#include <iostream>
#include <vector>
using namespace std;
#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
const int N = 200000 + 10;
int seen[10][N];
int seen2[10][N];
int used[12][N];
int sn = 0;
vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};
vector<int> a,b,X,Y;
vector<pair<int,int>> up,nup;
void dfs(int i,int j){
seen2[i][j] = true;
sn++;
for (auto [x,y] : d){
int ni = i + x;
int nj = j + y;
if (!seen[ni][nj] or seen2[ni][nj])
continue;
if (i==ni)
up.push_back({seen[i][j]-1,seen[ni][nj]-1});
else
nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
dfs(ni,nj);
}
}
pair<int,int> det(int x1,int y1,int x2,int y2){
if (x1 == x2){
if (y1>y2)
swap(y1,y2);
if (x1 == 2)
return {1,y1+1};
if (x1 == 6)
return {7,y1+1};
if (used[3][y1-1] or used[3][y2 + 1])
return {5,y1 + 1};
return {3,y1 + 1};
}
if (x1>x2)
swap(x1,x2);
if (used[x1+1][y1-1])
return {x1+1,y1+1};
return {x1+1,y1-1};
}
int construct_roads(vector<int> x,vector<int> y){
int n = x.size();
int mny = 1e7,k;
for (int i=0;i<n;i++){
seen[x[i]][y[i]] = i+1;
if (y[i]<mny)
mny = y[i],k = x[i];
}
dfs(k,mny);
if (sn!=n)
return 0;
for (auto [i,j] : up){
auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
used[ii][jj] = true;
a.push_back(i);
b.push_back(j);
X.push_back(ii);
Y.push_back(jj);
}
for (auto [i,j] : nup){
auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
used[ii][jj] = true;
a.push_back(i);
b.push_back(j);
X.push_back(ii);
Y.push_back(jj);
}
build(a,b,X,Y);
return 1;
}
