/*#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
const int N = 3e5+2;
vector<ll> points[N];
ll n;
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n = x.sz;
for(int i = 0; i < n; i++)
{
points[i] = {x[i],y[i],i};
}
sort(points,points+n);
vector<int> v1, v2, v3, v4;
for(int i = 1; i < n; i++)
{
if(points[i-1][1]+2!=points[i][1]) return 0;
v1.push_back(points[i-1][2]);
v2.push_back(points[i][2]);
v3.push_back(1);
v4.push_back(points[i][1]-1);
}
build(v1,v2,v3,v4);
return 1;
}*/
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define S second
#define F first
const int N = 3e5+2;
vector<ll> points[N];
ll n;
vector<int> v1,v2,v3,v4;
ll dx[] = {-2,0,2,0};
ll dy[] = {0,-2,0,2};
ll p[N];
pair<ll,ll> pos[N];
ll a[5][200005];
ll get(ll x)
{
if(x==p[x]) return x;
return p[x] = get(p[x]);
}
bool valid(ll x, ll y)
{
if(x==0||x==6) return 0;
if(y==0) return 0;
return 1;
}
void merg(ll x, ll y, ll k)
{
x = get(x); y = get(y);
if(x==y) return;
p[x] = y;
// 0 left , 1 down , 2 right, 3 up
v1.push_back(x-1);
v2.push_back(y-1);
ll midx, midy;
if(k==0||k==2)
{
midy = pos[x].S-1;
midx = 3;
}
else // down
{
if(pos[x].F==2)
{
midy = (pos[x].S+pos[y].S)/2;
midx = 1;
}
else
{
midy = (pos[x].S+pos[y].S)/2;
midx = 5;
}
}
v3.push_back(midx);
v4.push_back(midy);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n = x.sz;
// 1,2
for(int i = 0; i < n; i++)
{
a[x[i]][y[i]] = i+1;
pos[i+1] = {x[i],y[i]};
p[i+1] = i+1;
for(int k = 0; k < 4; k++)
{
ll newx = x[i] + dx[k] , newy = y[i] + dy[k];
if(valid(newx,newy)&&a[newx][newy]!=0)
{
merg(i+1,a[newx][newy],k);
}
}
}
ll cnt = 0;
for(int i = 1; i <= n; i++) if(p[i]==i) cnt++;
if(cnt>1) return 0;
build(v1,v2,v3,v4);
return 1;
}
