#include "parks.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
/*
For the vertical edges, use benches outside.
For the horizontal edges, use benches inside.
*/
vector<int> X, Y;
int N;
const int mx = 200000;
int construct_roads(vector<int> x, vector<int> y)
{
X = x;
Y = y;
N = X.size();
int fountain[5][1+mx];
for(int i: vector<int>{2, 4})
for(int j = 0; j <= mx; j++)
fountain[i][j] = -1;
for(int i = 0; i < N; i++)
{
fountain[ X[i] ][ Y[i] ] = i;
}
vector<int> U, V, A, B;
vector<int> edge[N];
for(int a = 2; a <= mx; a += 2)
{
if(a + 2 <= mx)
for(int x1: vector<int>{2, 4})
{
if(fountain[x1][a] != -1 && fountain[x1][a+2] != -1)
{
edge[ fountain[x1][a] ].push_back( fountain[x1][a+2] );
edge[ fountain[x1][a+2] ].push_back( fountain[x1][a] );
U.push_back(fountain[x1][a]);
V.push_back(fountain[x1][a+2]);
A.push_back(x1 == 2 ? 1 : 5);
B.push_back(a+1);
}
}
if(fountain[2][a] != -1 && fountain[4][a] != -1)
{
edge[fountain[2][a]].push_back(fountain[4][a]);
edge[fountain[4][a]].push_back(fountain[2][a]);
U.push_back(fountain[2][a]);
V.push_back(fountain[4][a]);
A.push_back(3);
B.push_back(a-1);
}
}
queue<int> tbv;
vector<int> visit(N, 0);
tbv.push(0);
visit[0] = 1;
while(!tbv.empty())
{
int q = tbv.front();
tbv.pop();
for(int w: edge[q])
{
if(visit[w]) continue;
visit[w] = 1;
tbv.push(w);
}
}
for(int i = 0; i < N; i++)
{
if(!visit[i]) return 0;
}
build(U, V, A, B);
return 1;
}
