#include <bits/stdc++.h>
#define pb push_back
using namespace std;
constexpr static int SIZE = 200001;
vector<int> g[SIZE];
bitset<SIZE> visited;
vector<array<int, 2>> rows[SIZE];
vector<array<int, 2>> intervals[SIZE];
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
void configure_rows(const vector<int>& x, const vector<int>& y)
{
int n = x.size();
for (int i = 0; i < n; i++)
rows[y[i]].pb({x[i], i});
for (int i = 0; i < SIZE; i+=2)
sort(rows[i].begin(), rows[i].end());
}
void configure_intervals()
{
for (int y = 0; y < SIZE; y+=2)
{
if (rows[y].empty())
continue;
intervals[y].pb({rows[y][0][0], rows[y][0][0]});
for (int i = 1; i < rows[y].size(); i++)
{
if (intervals[y].back()[1] + 2 == rows[y][i][0])
{
intervals[y].back()[1] = rows[y][i][0];
g[rows[y][i-1][1]].pb(rows[y][i][1]);
g[rows[y][i][1]].pb(rows[y][i-1][1]);
}
else
{
intervals[y].pb({rows[y][i][0], rows[y][i][0]});
}
}
}
}
// Line from a1 to a2 and line from b1 to b2
// Checking intersection (touching also counts)
bool is_intersecting(int a1, int a2, int b1, int b2)
{
return (b2 >= a1 && a1 >= b1) || (b2 >= a2 && a2 >= b1) || (a2 >= b1 && b1 >= a1) || (a2 >= b2 && b2 >= a1);
}
void configure_horizontal_connections()
{
for (int y = 2; y < SIZE; y+=2)
{
int i = 0, j = 0;
while (i < intervals[y].size() && j < intervals[y-2].size())
{
if (is_intersecting(intervals[y][i][0], intervals[y][i][1], intervals[y-2][j][0], intervals[y-2][j][1]))
{
int x = max(intervals[y][i][0], intervals[y-2][j][0]);
array<int, 2> pos = {x, 0};
int a = (*lower_bound(rows[y].begin(), rows[y].end(), pos))[1];
int b = (*lower_bound(rows[y-2].begin(), rows[y-2].end(), pos))[1];
g[a].pb(b);
g[b].pb(a);
}
if (intervals[y][i][1] > intervals[y-2][j][1])
j++;
else
i++;
}
}
}
int node_sum = 0;
void dfs(int node)
{
visited[node] = true;
node_sum++;
for (int c : g[node])
if (!visited[c])
dfs(c);
}
void build_grid(const vector<int>& xv, const vector<int>& yv)
{
vector<int> u, v, a, b;
set<array<int, 2>> fountains;
for (int y = 0; y < SIZE; y+=2)
{
for (auto [x, node] : rows[y])
{
for (int c : g[node])
{
if (yv[c] != y || xv[c] > x)
continue;
int fx = x-1, fy = y-1;
if (fountains.find({fx, fy}) != fountains.end())
fy += 2;
assert(fountains.find({fx, fy}) == fountains.end());
u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
fountains.insert({fx, fy});
}
}
for (auto [x, node] : rows[y])
{
for (int c : g[node])
{
if (yv[c] <= y)
continue;
int fx = x-1, fy = y+1;
if (fountains.find({fx, fy}) != fountains.end())
fx += 2;
assert(fountains.find({fx, fy}) == fountains.end());
u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
fountains.insert({fx, fy});
}
}
}
build(u, v, a, b);
}
int construct_roads(vector<int> x, vector<int> y)
{
configure_rows(x, y);
configure_intervals();
configure_horizontal_connections();
dfs(0);
if (node_sum < x.size())
return 0;
else
build_grid(x, y);
return 1;
}
