#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
vector<int> par;
int tot;
DSU(int n):tot(n){
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int node){
if (par[node]==node) return node;
return par[node]=find(par[node]);
}
bool merge(int a, int b){
a=find(a);
b=find(b);
if (a!=b) tot--;
else return false;
par[a]=b;
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
bool subtask3 = true;
int n = x.size();
for (int i = 0; i < n; i++){
if (x[i]<2 || x[i]>6) subtask3=false;
}
if (subtask3){
map<pair<int,int>,int> mp;
for (int i = 0; i < n; ++i)
{
mp[{x[i],y[i]}]=i;
}
DSU dsu(n);
vector<int> u;
vector<int> v;
vector<int> xa;
vector<int> ya;
set<pair<int,int>> occupied;
vector<int> lol;
for (int i = 0; i < n; i++){
if (mp.count({x[i],y[i]-2})){
if (dsu.merge(i,mp[{x[i],y[i]-2}])){
u.push_back(mp[{x[i],y[i]-2}]);
v.push_back(i);
ya.push_back(y[i]-1);
if (x[i]==2) xa.push_back(x[i]-1);
else if (x[i]==6) xa.push_back(x[i]+1);
else {
xa.push_back(-1);
lol.push_back(x[i]);
}
if (xa.back()!=-1) occupied.insert({xa.back(),ya.back()});
}
}
}
for (int i = 0; i < n; ++i)
{
if (x[i]==6){
if (mp.count({x[i]-2,y[i]})){
if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
u.push_back(mp[{x[i]-2,y[i]}]);
v.push_back(i);
xa.push_back(x[i]-1);
ya.push_back(y[i]-1);
occupied.insert({xa.back(),ya.back()});
}
}
}
}
for (int i = 0; i < n; ++i)
{
if (x[i]!=6){
if (mp.count({x[i]-2,y[i]})){
if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
u.push_back(mp[{x[i]-2,y[i]}]);
v.push_back(i);
xa.push_back(x[i]-1);
if (occupied.find({x[i]+1,y[i]-1})==occupied.end()){
ya.push_back(y[i]-1);
}
else ya.push_back(y[i]+1);
occupied.insert({xa.back(),ya.back()});
}
}
}
}
reverse(lol.begin(), lol.end());
bool boolean=true;
for (int i = 0; i < xa.size(); i++){
if (xa[i]==-1){
if (occupied.find({lol.back()+1,ya[i]})==occupied.end()){
xa[i]=lol.back()+1;
}
else if (occupied.find({lol.back()-1,ya[i]})==occupied.end()){
xa[i]=lol.back()-1;
}
else {
boolean=false;
break;
}
lol.pop_back();
}
}
if (dsu.tot==1 && boolean) {
return build(u,v,xa,ya),1;
}
return 0;
}
//subtasks 4..5
DSU dsu(n);
map<pair<int,int>, int>mp;
for (int i = 0; i < n; ++i)
{
mp[{x[i],y[i]}]=i;
}
vector<int> u;
vector<int> v;
vector<int> xa(n-1,-1);
vector<int> ya(n-1,-1);
vector<set<pair<int,int>>> arr;
map<pair<int,int>,set<int>> qu;
for (int i = 0; i < n; ++i)
{
if (mp.count({x[i]-2,y[i]})){
if (dsu.merge(mp[{x[i]-2,y[i]}],i)){
u.push_back(mp[{x[i]-2,y[i]}]);
v.push_back(i);
arr.push_back(set<pair<int,int>>());
arr.back().insert({x[i]-1,y[i]-1});
arr.back().insert({x[i]-1,y[i]+1});
qu[{x[i]-1,y[i]-1}].insert(u.size()-1);
qu[{x[i]-1,y[i]+1}].insert(u.size()-1);
}
}
if (mp.count({x[i],y[i]-2})){
if (dsu.merge(mp[{x[i],y[i]-2}],i)){
u.push_back(mp[{x[i],y[i]-2}]);
v.push_back(i);
arr.push_back(set<pair<int,int>>());
arr.back().insert({x[i]-1,y[i]-1});
arr.back().insert({x[i]+1,y[i]-1});
qu[{x[i]-1,y[i]-1}].insert(u.size()-1);
qu[{x[i]+1,y[i]-1}].insert(u.size()-1);
}
}
}
if (dsu.tot!=1) return 0;
vector<pair<int,int>> iki;
queue<pair<int,int>> que;
int kal = n-1;
for (auto it : qu){
if (it.second.size()==1) que.push(it.first);
else iki.push_back(it.first);
}
set<pair<int,int>> lmao;
while (kal>0){
if (!que.size()){
while (iki.size() && qu[iki.back()].size()<2) iki.pop_back();
if (iki.size()){
auto it = qu[iki.back()].begin();
arr[*it].erase(iki.back());
qu[iki.back()].erase(it);
que.push(iki.back());
iki.pop_back();
}
else return 0;
}
while (que.size() && qu[que.front()].size()<1 && lmao.find(que.front())!=lmao.end()) que.pop();
pair<int,int> pr = que.front();
que.pop();
//bu elemani baglicam kalanina bakarik
int it = *qu[pr].begin();
if (xa[it]!=-1) continue;
kal--;
lmao.insert(pr);
xa[it]=pr.first, ya[it]=pr.second;
for (auto it2 : arr[it]){
if (qu[it2].find(it)!=qu[it2].end()) qu[it2].erase(it);
if (qu[it2].size()==1) {
que.push(it2);
}
}
while (arr[it].size()) arr[it].erase(arr[it].begin());
}
build(u,v,xa,ya);
return 1;
}
