//
#ifndef __SIZEOF_INT128__
#define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
string name{""};
time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
duration<float, std::milli> dur;
Timer() = default;
Timer(string nm): name(nm) {}
~Timer() {
end = high_resolution_clock::now(); dur= end - start;
cout << "@" << name << "> " << dur.count() << " ms" << '\n';
}
};
template <typename T = int> inline T in()
{
static T x;
std::cin >> x;
return x;
}
std::string yn(bool b)
{
if(b) return "YES\n";
else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
for(const auto& i : wek)out << i << ' ';
return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
out << '{'<<par.first<<", "<<par.second<<"}";
return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include "parks.h"
constexpr int maxn =2e5 + 3;
int rep[maxn];
int find(int w)
{
if(!rep[w])return w;
return rep[w] = find(rep[w]);
}
int uni_c(0);
void uni(int a, int b){
a = find(a); b = find(b);
if(a != b){
rep[a] = b;
++uni_c;
}
}
vector <pair <int, int>> graf[maxn];
bool byl[maxn];
int construct_roads(vector <int> x, vector <int> y)
{
int n(sz(x));
map <pair <int, int>, int> s;
rep(i, 0, n)s[{x[i], y[i]}] = i+1;
int m(0);
map <pair <pair <int, int>, pair <int, int>>, int> k;
vector <pair <pair <int, int>, pair <int, int>>> lk;
vector <pair <int, int>> dld;
rep(i, 0, n){
if(s.count({x[i]+2, y[i]})){
uni(i+1, s[{x[i]+2, y[i]}]);
k[{{x[i],y[i]},{x[i]+2, y[i]}}] = ++m;
lk.push_back({{x[i],y[i]},{x[i]+2, y[i]}});
dld.pb(i, s[{x[i]+2, y[i]}]-1);
}
if(s.count({x[i], y[i]+2})){
uni(i+1, s[{x[i], y[i]+2}]);
k[{{x[i],y[i]},{x[i], y[i]+2}}] = ++m;
lk.push_back({{x[i],y[i]},{x[i], y[i]+2}});
dld.pb(i, s[{x[i], y[i]+2}]-1);
}
}
if(uni_c != n-1)return 0;
vector <pair <int, int>> v;
map <pair <int, int>, int> nm;
rep(i, 0, n) if(s.count({x[i]+2, y[i]}) && s.count({x[i], y[i]+2}) && s.count({x[i]+2, y[i]+2})){
v.pb(x[i]+1, y[i]+1);
nm[{x[i]+1, y[i]+1}] = sz(v);
}
rep(i, 0, sz(v)){
auto [x, y] = v[i];
if((x/2 + y/2) % 2){
graf[i+1].pb(nm[{x-2, y}], k[{{x-1, y-1}, {x-1, y+1}}]);
graf[i+1].pb(nm[{x+2, y}], k[{{x+1, y-1}, {x+1, y+1}}]);
graf[nm[{x, y-2}]].pb(i+1, k[{{x-1, y-1}, {x+1, y-1}}]);
graf[nm[{x, y+2}]].pb(i+1, k[{{x-1, y+1}, {x+1, y+1}}]);
}
else{
graf[i+1].pb(nm[{x, y-2}], k[{{x-1, y-1}, {x+1, y-1}}]);
graf[i+1].pb(nm[{x, y+2}], k[{{x-1, y+1}, {x+1, y+1}}]);
graf[nm[{x-2, y}]].pb(i+1, k[{{x-1, y-1}, {x-1, y+1}}]);
graf[nm[{x+2, y}]].pb(i+1, k[{{x+1, y-1}, {x+1, y+1}}]);
}
}
// rep(i, 0, sz(v)+1)for(auto [j, kk]: graf[i])cout << (i ? v[i-1] : pair<int, int>{-1, -1} ) << ' ' << (j ? v[j-1] : pair<int, int>{-1,-1}) << ' ' << lk[kk-1] << '\n';
stack <int> dfs; dfs.push(0);
vector <bool> us(sz(lk));
byl[0] = 1;
while(dfs.size()){
int w(dfs.top()); dfs.pop();
for(auto [i, j]: graf[w])if(!byl[i]){
byl[i] = 1;
dfs.push(i);
us[j-1] = 1;
}
}
vector <int> ru, rv, ra, rb;
rep(i, 0, sz(lk))if(!us[i]){
auto [a, b] = dld[i];
ru.pb(a);
rv.pb(b);
if(x[a] == x[b]){
if((x[a]/2 + y[a]/2) % 2){
ra.pb(x[a]-1);
rb.pb(y[a]+1);
}
else{
ra.pb(x[a]+1);
rb.pb(y[a]+1);
}
}
else{
if((x[a]/2 + y[a]/2) % 2){
ra.pb(x[a]+1);
rb.pb(y[a]+1);
}
else{
ra.pb(x[a]+1);
rb.pb(y[a]-1);
}
}
}
build(ru, rv, ra, rb);
return 1;
}
