#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 400005;
int n;
vector<int> g[N];
bool c[N];
vector<int> uu, vv;
void dfs(int x)
{
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (c[h])
continue;
uu.push_back(x);
vv.push_back(g[x][i]);
dfs(h);
}
}
vector<pair<int, int> > rs;
vector<int> gg[N], gi[N];
void dfs(int x, vector<int>& a, vector<int>& b)
{
c[x] = true;
for (int i = 0; i < gg[x].size(); ++i)
{
int h = gg[x][i];
if (a[gi[x][i]] == -1)
{
a[gi[x][i]] = rs[x].fi;
b[gi[x][i]] = rs[x].se;
}
if (!c[h])
dfs(h, a, b);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
std::vector<int> u, v, a, b;
n = sz(x);
vector<pair<int, int> > p;
map<pair<int, int>, int> mp;
for (int i = 0; i < n; ++i)
{
p.push_back(m_p(x[i], y[i]));
mp[m_p(x[i], y[i])] = i;
}
int z = 0;
map<pair<int, int>, int> s;
for (int i = 0; i < n; ++i)
{
int x = p[i].fi;
int y = p[i].se;
if (mp.find(m_p(x + 2, y)) != mp.end())
{
u.push_back(mp[m_p(x, y)]);
v.push_back(mp[m_p(x + 2, y)]);
if (s.find(m_p(x + 1, y + 1)) == s.end())
s[m_p(x + 1, y + 1)] = z++;
if (s.find(m_p(x + 1, y - 1)) == s.end())
s[m_p(x + 1, y - 1)] = z++;
g[u.back()].push_back(v.back());
g[v.back()].push_back(u.back());
gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x + 1, y - 1)]);
gg[s[m_p(x + 1, y - 1)]].push_back(s[m_p(x + 1, y + 1)]);
gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
gi[s[m_p(x + 1, y - 1)]].push_back(sz(u) - 1);
}
if (mp.find(m_p(x, y + 2)) != mp.end())
{
u.push_back(mp[m_p(x, y)]);
v.push_back(mp[m_p(x, y + 2)]);
if (s.find(m_p(x + 1, y + 1)) == s.end())
s[m_p(x + 1, y + 1)] = z++;
if (s.find(m_p(x - 1, y + 1)) == s.end())
s[m_p(x - 1, y + 1)] = z++;
g[u.back()].push_back(v.back());
g[v.back()].push_back(u.back());
gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x - 1, y + 1)]);
gg[s[m_p(x - 1, y + 1)]].push_back(s[m_p(x + 1, y + 1)]);
gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
gi[s[m_p(x - 1, y + 1)]].push_back(sz(u) - 1);
}
}
rs.assign(z, m_p(0, 0));
for (auto it = s.begin(); it != s.end(); ++it)
{
rs[it->se] = it->fi;
}
dfs(0);
for (int i = 0; i < n; ++i)
{
if (!c[i])
return 0;
}
int maxu = 0;
for (int i = 0; i < n; ++i)
{
maxu = max(maxu, x[i]);
}
memset(c, false, sizeof c);
a.assign(sz(u), -1);
b.assign(sz(u), -1);
if (maxu <= 6)
{
u = uu;
v = vv;
a.assign(sz(u), -1);
b.assign(sz(u), -1);
vector<pair<pair<int, int>, int> > p;
for (int i = 0; i < sz(u); ++i)
{
int mx = (x[u[i]] + x[v[i]]) / 2;
int my = (y[u[i]] + y[v[i]]) / 2;
p.push_back(m_p(m_p(my, mx), i));
}
sort(all(p));
for (int i = 0; i < sz(u); ++i)
{
uu[i] = u[p[i].se];
vv[i] = v[p[i].se];
}
u = uu;
v = vv;
for (int i = 0; i < sz(u); ++i)
{
int mx = (x[u[i]] + x[v[i]]) / 2;
int my = (y[u[i]] + y[v[i]]) / 2;
if (mx % 2 == 0)
{
if (!c[s[m_p(mx - 1, my)]])
{
a[i] = mx - 1;
b[i] = my;
c[s[m_p(mx - 1, my)]] = true;
}
else
{
assert(!c[s[m_p(mx + 1, my)]]);
a[i] = mx + 1;
b[i] = my;
c[s[m_p(mx + 1, my)]] = true;
}
}
else
{
assert(my % 2 == 0);
if (!c[s[m_p(mx, my - 1)]])
{
a[i] = mx;
b[i] = my - 1;
c[s[m_p(mx, my - 1)]] = true;
}
else
{
assert(!c[s[m_p(mx, my + 1)]]);
a[i] = mx;
b[i] = my + 1;
c[s[m_p(mx, my + 1)]] = true;
}
}
}
}
else
{
for (int i = 0; i < z; ++i)
{
if (!c[i] && sz(gg[i]) == 1)
{
dfs(i, a, b);
}
}
for (int i = 0; i < z; ++i)
{
if (!c[i])
{
dfs(i, a, b);
}
}
}
build(u, v, a, b);
return 1;
}
/*
3
2 2
4 4
2 4
3
2 2
4 2
2 4
3
4 2
2 2
4 4
3
4 4
4 2
2 4
9
4 2
4 4
2 2
2 4
2 6
4 6
2 8
4 8
4 10
*/
