#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int N=1e3+9;
vector<int> rnk(N,0),par(N);
int ulp(int node){
if(par[node]==node) return node;
return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
a=ulp(a);b=ulp(b);
if(a==b) return;
if(rnk[b]>rnk[a])
swap(a,b);
par[b]=a;
if(rnk[a]==rnk[b])
rnk[a]++;
}
int construct(std::vector<std::vector<int>> p){
n=p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector<set<int>> lanci(n);
for(int i=0; i<n; i++) par[i]=i;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j]==1)
spajaj(i,j);
if(p[i][j]==3) return 0;
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j]==1){
lanci[ulp(i)].insert(j);
lanci[ulp(i)].insert(i);
}
if(ulp(i)==ulp(j)&&p[i][j]!=1)
return 0;
}
}
for(int i=0; i<n; i++){
if(lanci[i].size()<=1) continue;
for(auto it=next(lanci[i].begin()); it!=lanci[i].end(); it++){
answer[*prev(it)][*it]=1;
answer[*it][*prev(it)]=1;
}
}
vector<int> br_poj_predstavnika(n,0);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j]!=2) continue;
if(br_poj_predstavnika[ulp(i)]==2||br_poj_predstavnika[ulp(j)]==2) continue;
//cout << i << " " << j << endl;
br_poj_predstavnika[ulp(i)]++;
br_poj_predstavnika[ulp(j)]++;
answer[ulp(i)][ulp(j)]=1;
answer[ulp(j)][ulp(i)]=1;
}
}
build(answer);
return 1;
}
