#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();
map<pair<int,int>,int> mp;
for (int i = 0; i < n; i++){
mp[{x[i],y[i]}]=i;
if (x[i]<2 || x[i]>6) subtask3=false;
}
if (subtask3){
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;
}
else return cout<<"WA"<<endl,0;
}
