#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>p;
int find(int x){
if (x==p[x]) return x;
else return p[x]=find(p[x]);
}
bool Union(int x, int y){
int a=find(x), b=find(y);
if(a==b) return false;
else p[a]=b;
return true;
}
dsu(int n){
p.resize(n);
for(int i=0;i<n;i++) p[i]=i;
}
};
int construct(std::vector<std::vector<int>> p) {
int n=p.size();
vector<vector<int>>ans(n,vector<int>(n));
dsu todo(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3) return 0;
if(p[i][j]==1) todo.Union(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!p[i][j] && todo.find(i)==todo.find(j))return 0;
}
}
for(int i=0;i<n;i++){
vector<int>gr;
for(int j=0;j<n;j++){
if(todo.find(j)==i)gr.push_back(j);
}
if(gr.size()<2)continue;
dsu orden(n);
for(int j=0;j<gr.size();j++){
for(int k=j+1;k<gr.size();k++){
int a=gr[j], b=gr[k];
if(p[a][b]==1){
if(orden.Union(a,b)){
ans[a][b]=ans[b][a]=1;
}
}
}
}
for(int j=0;j<gr.size();j++){
for(int k=j+1;k<gr.size();k++){
int a=gr[j], b=gr[k];
if(p[a][b]==2 && orden.find(a)==orden.find(b))return 0;
}
}
vector<int> subgr;
for(int j=0;j<gr.size();j++){
if(orden.find(gr[j])==gr[j])subgr.push_back(gr[j]);
}
if(subgr.size()==1)continue;
if(subgr.size()==2)return 0;
for(int j=1;j<subgr.size();j++){
ans[subgr[j-1]][subgr[j]]=1;
ans[subgr[j]][subgr[j-1]]=1;
}
ans[subgr[0]][subgr.back()]=1;
ans[subgr.back()][subgr[0]]=1;
}
build(ans);
return 1;
}
