#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
int n;
vector<int> parent,sz;
DSU(int _n){
n = _n;
for(int i=0;i<=n;i++){
parent.push_back(i);
sz.push_back(1);
}
}
int find(int x){
return parent[x] = (parent[x] == x ? x : find(parent[x]));
}
void unite(int a,int b){
a = find(a);
b = find(b);
if(a != b){
if(sz[a] >= sz[b]){
parent[b] = a;
sz[a] += sz[b];
}else{
parent[a] = b;
sz[b] += sz[a];
}
}
}
};
int construct(vector<vector<int>> p) {
// 30
int n = p.size();
vector<vector<int>> answer(n,vector<int>(n,0));
DSU comp(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 3 || p[i][j] == 1)return 0;
if(p[i][j] == 2)comp.unite(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
}
}
vector<bool> vis(n,0);
map<int,vector<int>> comps;
for(int i=0;i<n;i++){
comps[comp.find(i)].push_back(i);
}
for(auto i:comps){
vector<int> &p = i.second;
if((int)p.size() == 2)return 0;
if((int)p.size() < 2)continue;
for(int i=1;i<(int)p.size();i++){
answer[p[i]][p[i-1]] = answer[p[i-1]][p[i]] = 1;
}
answer[p[(int)p.size()-1]][p[0]] = answer[p[0]][p[(int)p.size()-1]] = 1;
}
build(answer);
return 1;
}
