#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
struct dsu{
int n;
vector<int>sz,par;
dsu(int n):n(n){
sz.resize(n);
par.resize(n);
fill(all(sz),1);
iota(all(par),0);
}
int find(int x){
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
if(sz[x]<sz[y]){
swap(x,y);
}
sz[x]+=sz[y];
par[y]=x;
}
}
bool same(int x,int y){
x=find(x);
y=find(y);
return x==y;
}
};
int construct(vector<vector<int>>p){
int n=p.size();
dsu ds(n),ds_cmp(n);
vector<vector<int>>b(n,vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]>0){
ds_cmp.merge(i,j);
}
if(p[i][j]==1){
if(!ds.same(i,j)){
b[i][j]=1;
b[j][i]=1;
ds.merge(i,j);
}
}
}
}
set<int>group[n];
for(int i=0;i<n;i++){
group[ds_cmp.find(i)].insert(ds.find(i));
}
vector<int>g[n];
for(int i=0;i<n;i++){
g[i]=vector<int>(all(group[i]));
int sz=g[i].size();
if(sz<2) continue;
if(sz==2) return 0;
for(int j=0;j<sz;j++){
b[g[i][j]][g[i][(j+1)%sz]]=1;
b[g[i][(j+1)%sz]][g[i][j]]=1;
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]!=1&&ds.same(i,j)) return 0;
if(p[i][j]!=2&&p[i][j]!=0&&!ds.same(i,j)) return 0;
if(p[i][j]==0&&ds_cmp.same(i,j)) return 0;
}
}
build(b);
return 1;
}
