#include <bits/stdc++.h>
#include "parks.h"
#define mp make_pair
#define X first
#define Y second
#define all(a) a.begin(),a.end()
using namespace std;
using pii = pair <int, int>;
const int maxn = 5e5 + 10;
int par [maxn];
inline int get (int x) {
if (par[x] == x) return x;
return par[x] = get (par[x]);
}
inline void unite (int x, int y) {
x = get (x), y = get (y);
par[x] = y;
}
vector <int> graph [maxn][2];
bool used [maxn][2];
vector <int> u, v, c, d;
vector <pii> xx [maxn], yy [maxn];
map <pii, int> mas;
int timer = 0;
int K [maxn], M [maxn], result [maxn];
vector <int> way = {};
inline void dfs (int v, bool B) {
way.push_back (v);
used[v][B] = true;
for (int i : graph[v][B]) if (!used[i][!B]) dfs (i, !B);
}
int construct_roads (vector <int> a, vector <int> b) {
int n = (int) a.size ();
for (int i = 0; i < n; ++i) par[i] = i;
vector <int> _b = a;
sort (all (_b));
int L = _b[0], R = _b.back ();
for (int i = 0; i < n; ++i) xx[a[i]].push_back (mp (b[i], i)), yy[b[i]].push_back (mp (a[i], i));
for (int i = L; i <= R; i += 2) {
sort (all (xx[i]));
int N = (int) xx[i].size ();
for (int j = 0; j < N - 1; ++j) if (xx[i][j].X + 2 == xx[i][j + 1].X) {
int U = xx[i][j].Y, V = xx[i][j + 1].Y;
//cout << "! " << U << ' ' << V << '\n';
if (get (U) == get (V)) continue;
u.push_back (U);
v.push_back (V);
unite (U, V);
}
}
_b = b;
sort (all (_b));
L = _b[0], R = _b.back ();
for (int i = L; i <= R; i += 2) {
sort (all (yy[i]));
int N = (int) yy[i].size ();
for (int j = 0; j < N - 1; ++j) if (yy[i][j].X + 2 == yy[i][j + 1].X) {
int U = yy[i][j].Y, V = yy[i][j + 1].Y;
if (get (U) == get (V)) continue;
u.push_back (U);
v.push_back (V);
unite (U, V);
}
}
if ((int) u.size () != n - 1) return 0;
for (int i = 0; i < n - 1; ++i) {
int m1, m2;
if (a[u[i]] == a[v[i]]) {
m1 = a[u[i]], m2 = b[u[i]] + b[v[i]] >> 1;
++m1;
if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
graph[i][0].push_back (mas[mp (m1, m2)]);
graph[mas[mp (m1, m2)]][1].push_back (i);
m1 -= 2;
if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
graph[i][0].push_back (mas[mp (m1, m2)]);
graph[mas[mp (m1, m2)]][1].push_back (i);
} else {
m1 = a[u[i]] + a[v[i]] >> 1, m2 = b[u[i]];
++m2;
if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
graph[i][0].push_back (mas[mp (m1, m2)]);
graph[mas[mp (m1, m2)]][1].push_back (i);
m2 -= 2;
if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
graph[i][0].push_back (mas[mp (m1, m2)]);
graph[mas[mp (m1, m2)]][1].push_back (i);
}
}
for (int i = 0; i < timer; ++i) if (graph[i][1].size () == 1 && !used[i][1]) {
way.clear ();
dfs (i, 1);
int N = (int) way.size ();
for (int j = 0; j + 1 < (int) way.size (); j += 2) result[way[j + 1]] = way[j];
}
for (int i = 0; i < timer; ++i) if (!used[i][1]) {
way.clear ();
dfs (i, 1);
int N = (int) way.size ();
for (int j = 0; j + 1 < (int) way.size (); j += 2) result[way[j + 1]] = way[j];
}
for (int i = 0; i < n - 1; ++i) c.push_back (K[result[i]]), d.push_back (M[result[i]]);
build (u, v, c, d);
return 1;
}
