#include "parks.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int nn;
vector < int > p[maxn];
vector < pair < int, int > > h[maxn];
int used[maxn], seen;
void dfs(int beg, int from)
{
used[beg] = 1;
seen ++;
for(auto nb: p[beg])
{
if(used[nb])continue;
dfs(nb, beg);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y)
{
if (x.size() == 1)
{
build({}, {}, {}, {});
return 1;
}
nn = x.size();
vector < pair < int, int > > g[5];
for (int i = 0; i < nn; ++ i)
{
if(x[i] == 2)g[2].pb(make_pair(y[i], i));
if(x[i] == 4)g[4].pb(make_pair(y[i], i));
h[y[i]].pb(make_pair(x[i], i));
}
sort(g[2].begin(), g[2].end());
sort(g[4].begin(), g[4].end());
std::vector<int> u, v, a, b;
for (int i = 0 ; i < g[2].size(); ++ i)
{
if(i == 0)continue;
if(g[2][i].first - g[2][i-1].first != 2)continue;
int index1 = g[2][i].second;
int index2 = g[2][i-1].second;
p[index1].pb(index2);
p[index2].pb(index1);
u.pb(index1);
v.pb(index2);
a.pb(0);
b.pb(g[2][i].first - 1);
}
for (int i = 0 ; i < g[4].size(); ++ i)
{
if(i == 0)continue;
if(g[4][i].first - g[4][i-1].first != 2)continue;
int index1 = g[4][i].second;
int index2 = g[4][i-1].second;
p[index1].pb(index2);
p[index2].pb(index1);
u.pb(index1);
v.pb(index2);
a.pb(5);
b.pb(g[4][i].first - 1);
}
for (int i = 1; i <= 2e5; ++ i)
{
if(h[i].size() == 2)
{
int index1 = h[i][0].second;
int index2 = h[i][1].second;
p[index1].pb(index2);
p[index2].pb(index1);
u.pb(index1);
v.pb(index2);
a.pb(3);
b.pb(i-1);
}
}
dfs(0, -1);
if(seen != nn)return 0;
build(u, v, a, b);
return 1;
}
