#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];
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;
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;
vector<int> vv[2];
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);
vv[0].push_back(s[m_p(x + 1, y + 1)]);
vv[1].push_back(s[m_p(x + 1, y - 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);
vv[0].push_back(s[m_p(x + 1, y + 1)]);
vv[1].push_back(s[m_p(x - 1, y + 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]);
maxu = max(maxu, y[i]);
}
memset(c, false, sizeof c);
a.assign(sz(u), -1);
b.assign(sz(u), -1);
if (maxu <= 6)
{
for (int x = 0; x < (1 << sz(u)); ++x)
{
for (int i = 0; i < sz(u); ++i)
{
if (!(x & (1 << i)))
{
a[i] = rs[vv[0][i]].fi;
b[i] = rs[vv[0][i]].se;
}
else
{
a[i] = rs[vv[1][i]].fi;
b[i] = rs[vv[1][i]].se;
}
}
vector<pair<int, int> > s;
for (int i = 0; i < sz(u); ++i)
s.push_back(m_p(a[i], b[i]));
sort(all(s));
bool f = true;
for (int i = 0; i < sz(s) - 1; ++i)
{
if (s[i] == s[i + 1])
{
f = false;
break;
}
}
if (f)
break;
}
vector<pair<int, int> > s;
for (int i = 0; i < sz(u); ++i)
s.push_back(m_p(a[i], b[i]));
sort(all(s));
bool f = true;
for (int i = 0; i < sz(s) - 1; ++i)
{
if (s[i] == s[i + 1])
{
f = false;
break;
}
}
assert(f);
}
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 2
2 4
3
4 2
2 2
4 4
3
4 4
4 2
2 4
4
4 2
4 4
2 2
2 4
*/
