#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct DSU{
int par[N], setsize[N], setcnt;
void reset(int n){
for(int i = 0; i < n; i++) par[i] = i, setsize[i] = 1;
setcnt = n;
}
int setfind(int a){
if(a == par[a]) return a;
else return par[a] = setfind(par[a]);
}
void setunion(int a, int b){
a = setfind(a), b = setfind(b);
if(a != b){
if(setsize[b] > setsize[a]) swap(a, b);
par[b] = par[a];
setsize[a] += setsize[b];
setcnt--;
}
}
};
DSU dsu;
struct Point{
int x, y;
bool operator < (const Point &sc) const{
if(x == sc.x) return y < sc.y;
else return x < sc.x;
}
};
int construct_roads(vector<int> xvec, vector<int> yvec){
int n = xvec.size();
dsu.reset(n);
map<Point, int> nodes;
map<Point, Point> edges;
map<Point, bool> vis;
for(int i = 0; i < n; i++) nodes[{xvec[i], yvec[i]}] = i;
if(*max_element(xvec.begin(), xvec.end()) <= 2){ // subtask 1
for(auto p : nodes){
Point po = p.first;
if(nodes.find({2, po.y + 2}) != nodes.end()){
edges[{p.second, nodes[{2, po.y + 2}]}] = {1, po.y + 1};
dsu.setunion(p.second, nodes[{2, po.y + 2}]);
}
}
}
else if(*max_element(xvec.begin(), xvec.end()) <= 4){ // subtask 2
vector<int> x2, x4;
for(int i = 0; i < n; i++){
if(xvec[i] == 2) x2.push_back(yvec[i]);
else if(xvec[i] == 4) x4.push_back(yvec[i]);
}
sort(x2.begin(), x2.end());
sort(x4.begin(), x4.end());
for(auto y : x2){
if(nodes.find({2, y + 2}) != nodes.end()){
edges[{nodes[{2, y}], nodes[{2, y + 2}]}] = {1, y + 1};
dsu.setunion(nodes[{2, y}], nodes[{2, y + 2}]);
}
}
for(auto y : x4){
if(nodes.find({4, y + 2}) != nodes.end()){
edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {5, y + 1};
dsu.setunion(nodes[{4, y}], nodes[{4, y + 2}]);
}
if(nodes.find({2, y}) != nodes.end()){
edges[{nodes[{4, y}], nodes[{2, y}]}] = {3, y + 1};
dsu.setunion(nodes[{4, y}], nodes[{2, y}]);
}
}
}
else if(*max_element(xvec.begin(), xvec.end()) <= 6){ // subtask 3
vector<int> x2, x4, x6;
for(int i = 0; i < n; i++){
if(xvec[i] == 2) x2.push_back(yvec[i]);
else if(xvec[i] == 4) x4.push_back(yvec[i]);
else if(xvec[i] == 6) x6.push_back(yvec[i]);
}
sort(x2.begin(), x2.end());
sort(x4.begin(), x4.end());
sort(x6.begin(), x6.end());
for(auto y : x2){
if(nodes.find({2, y + 2}) != nodes.end()){
edges[{nodes[{2, y}], nodes[{2, y + 2}]}] = {1, y + 1};
dsu.setunion(nodes[{2, y}], nodes[{2, y + 2}]);
}
}
for(auto y : x6){
if(nodes.find({6, y + 2}) != nodes.end()){
edges[{nodes[{6, y}], nodes[{6, y + 2}]}] = {7, y + 1};
dsu.setunion(nodes[{6, y}], nodes[{6, y + 2}]);
}
}
for(auto y : x4){
if(nodes.find({4, y + 2}) != nodes.end()){
dsu.setunion(nodes[{4, y}], nodes[{4, y + 2}]);
}
}
for(auto y : x4){
if(nodes.find({6, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{6, y}])){
edges[{nodes[{4, y}], nodes[{6, y}]}] = {5, y - 1};
vis[{5, y - 1}] = true;
dsu.setunion(nodes[{4, y}], nodes[{6, y}]);
if(nodes.find({2, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{2, y}])){
edges[{nodes[{2, y}], nodes[{4, y}]}] = {3, y + 1};
vis[{3, y + 1}] = true;
dsu.setunion(nodes[{2, y}], nodes[{4, y}]);
}
}
else if(nodes.find({2, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{2, y}])){
edges[{nodes[{2, y}], nodes[{4, y}]}] = {3, y - 1};
vis[{3, y - 1}] = true;
dsu.setunion(nodes[{2, y}], nodes[{4, y}]);
}
}
for(auto y : x4){
if(nodes.find({4, y + 2}) != nodes.end()){
if(!vis[{3, y + 1}]){
edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {3, y + 1};
}
else if(!vis[{5, y + 1}]){
edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {5, y + 1};
}
// else assert(false);
}
}
}
else{ // subtask 4, 5
queue<Point> que;
Point fpo = nodes.begin()->first;
if(nodes.find({fpo.x + 2, fpo.y}) != nodes.end()){
edges[{nodes.begin()->second, nodes[{fpo.x + 2, fpo.y}]}] = {fpo.x + 1, fpo.y - 1};
dsu.setunion(nodes.begin()->second, nodes[{fpo.x + 2, fpo.y}]);
que.push({fpo.x + 1, fpo.y - 1});
}
else if(nodes.find({fpo.x, fpo.y + 2}) != nodes.end()){
edges[{nodes.begin()->second, nodes[{fpo.x, fpo.y + 2}]}] = {fpo.x - 1, fpo.y + 1};
dsu.setunion(nodes.begin()->second, nodes[{fpo.x, fpo.y + 2}]);
que.push({fpo.x - 1, fpo.y + 1});
}
while(!que.empty()){
Point p = que.front(); que.pop();
if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && !vis[{p.x - 2, p.y}]){
edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x - 1, p.y + 1}]}] = {p.x - 2, p.y};
vis[{p.x - 2, p.y}] = true;
que.push({p.x - 2, p.y});
}
if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y - 1}) != nodes.end() && !vis[{p.x, p.y - 2}]){
edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x + 1, p.y - 1}]}] = {p.x, p.y - 2};
vis[{p.x, p.y - 2}] = true;
que.push({p.x, p.y - 2});
}
if(nodes.find({p.x + 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y + 1}) != nodes.end() && !vis[{p.x + 2, p.y}]){
edges[{nodes[{p.x + 1, p.y - 1}], nodes[{p.x + 1, p.y + 1}]}] = {p.x + 2, p.y};
vis[{p.x + 2, p.y}] = true;
que.push({p.x + 2, p.y});
}
if(nodes.find({p.x + 1, p.y + 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && !vis[{p.x, p.y + 2}]){
edges[{nodes[{p.x + 1, p.y + 1}], nodes[{p.x - 1, p.y + 1}]}] = {p.x, p.y + 2};
vis[{p.x, p.y + 2}] = true;
que.push({p.x, p.y + 2});
}
}
}
if(dsu.setcnt == 1){
vector<int> vecs[4];
for(auto p : edges){
vecs[0].push_back(p.first.x);
vecs[1].push_back(p.first.y);
vecs[2].push_back(p.second.x);
vecs[3].push_back(p.second.y);
}
build(vecs[0], vecs[1], vecs[2], vecs[3]);
return 1;
}
else return 0;
}
