#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo;
void init(int x){
bo.resize(x);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
bo[x]=y;
}
}dsu,dsu2;
int construct(vector<vector<int> > p) {
int n=p.size();
dsu.init(n);
dsu2.init(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]){
dsu.merge(i,j);
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if((p[i][j]>0) + (dsu.find(i)==dsu.find(j))==1){
return 0;
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==1){
dsu2.merge(i,j);
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]){
if((p[i][j]==1) + (dsu2.find(i)==dsu2.find(j))==1){
return 0;
}
}
}
}
vector<int> val(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(dsu.find(i)==dsu.find(j)){
if(dsu2.find(i)!=dsu2.find(j)){
if(val[dsu.find(i)] && val[dsu.find(i)]!=p[i][j]){
return 0;
}
val[dsu.find(i)]=p[i][j];
}
}
}
}
vector<vector<int> > vx(n);
vector<vector<int> > bd(n,vector<int>(n));
for(int i=0;i<n;i++){
if(i!=dsu2.find(i)){
bd[i][dsu2.find(i)]=bd[dsu2.find(i)][i]=1;
}
else{
vx[dsu.find(i)].push_back(i);
}
}
for(int i=0;i<n;i++){
int y=vx[i].size();
if(y>=2){
if(val[i]==0){
return 0;
}
if(val[i]==2){
for(int j=0;j<y;j++){
bd[vx[i][j]][vx[i][(j+1)%y]]=bd[vx[i][(j+1)%y]][vx[i][j]]=1;
}
}
else if(val[i]==3){
if(y<=3){
return 0;
}
for(int j=0;j<y;j++){
bd[vx[i][j]][vx[i][(j+1)%y]]=bd[vx[i][(j+1)%y]][vx[i][j]]=1;
}
bd[vx[i][0]][vx[i][2]]=bd[vx[i][2]][vx[i][0]]=1;
}
}
}
build(bd);
return 1;
}
