#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()
typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
typedef pair <ll, ii> iii;
typedef vector <iii> viii;
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void printVct(vi &v){
for (ll i =0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
vector <vi> adj;
vi vis;
ll dfs(ll u){
vis[u] = 1;
ll ans = 1;
for (ll i= 0; i<sz(adj[u]); i++){
if (!vis[adj[u][i]]){
ans += dfs(adj[u][i]);
}
}
return ans;
}
void add_road(ll cur_id, ll prev_id, vi &u, vi &v){
// dbg2(cur_id, prev_id);
adj[cur_id].pb(prev_id);
adj[prev_id].pb(cur_id);
u.pb(prev_id);
v.pb(cur_id);
}
int construct_roads(vi x, vi y) {
ll n = sz(x);
vi u,v,a,b;
viii c;
for (ll i= 0; i<n; i++){
c.pb(iii(x[i], ii(y[i], i)));
}
sort(c.begin(),c.end());
adj.assign(n, vi());
ll prev = -10, p;
for (p = 0; p < n && c[p].F == 2; p++){
// dbg2(2,p);
if (c[p].S.F - prev == 2){
ll cur_id = c[p].S.S, prev_id = c[p-1].S.S;
add_road(prev_id, cur_id, u, v);
a.pb(1);
b.pb(c[p].S.F-1);
}
prev = c[p].S.F;
}
prev = -10;
for (; p < n; p++){
// dbg2(4, p);
if (c[p].S.F - prev == 2){
ll cur_id = c[p].S.S, prev_id = c[p-1].S.S;
add_road(prev_id, cur_id, u, v);
a.pb(5);
b.pb(c[p].S.F-1);
}
prev = c[p].S.F;
}
for (ll i =0; i<n; i++){
swap(c[i].F, c[i].S.F);
}
sort(c.begin(), c.end());
// cout<<endl<<endl;
prev = -10;
for (ll i= 0; i<n; i++){
if (c[i].F == prev){
// dbg2('u', i);
ll cur_id = c[i].S.S, prev_id = c[i-1].S.S;
add_road(prev_id, cur_id, u, v);
a.pb(3);
b.pb(c[i].F-1);
}
prev = c[i].F;
}
vis.assign(n, 0);
ll d = dfs(0);
if (d != n) return 0;
build(u, v, a, b);
return 1;
}
/*
2
2 2
2 4
4
4 4
4 6
4 2
2 4
*/
