#include"supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
vector<int> ds[MAXN],vi;
bool ck[MAXN],vis[MAXN];
int dsu[MAXN];
void dfs(int i)
{
ck[i]=true,vi.push_back(i);
for(auto v:ds[i]) if(!ck[v]) dfs(v);
}
int root(int i)
{
if(!dsu[i]) return i;
return dsu[i]=root(dsu[i]);
}
void merge(int i,int j)
{
if((i=root(i))==(j=root(j))) return ;
dsu[j]=i;
}
int construct(vector< vector<int> > p)
{
int n=p.size();
vector< vector<int> > ans(n);
for(int i=0;i<n;i++) ans[i].resize(n);
for(int i=0;i<n;i++) for(int j=0;j<n;j++)
{
if(p[i][j]) ds[i].push_back(j);
if(p[i][j]==3) return 0;
}
for(int i=0;i<n;i++) if(!ck[i])
{
vi.clear();
dfs(i);
bool ck=true;
for(auto v:vi) for(auto u:vi)
{
if(!p[v][u]) return 0;
ck&=(p[v][u]==1);
}
if(ck) for(int j=1;j<vi.size();j++) ans[vi[0]][vi[j]]=ans[vi[j]][vi[0]]=1;
else
{
vector<int> vp;
for(int j=0;j<vi.size();j++) for(int k=0;k<vi.size();k++) if(p[vi[j]][vi[k]]==1) merge(vi[j],vi[k]);
for(int j=0;j<vi.size();j++) for(int k=0;k<vi.size();k++) if((root(vi[j])==root(vi[k]))^(p[vi[j]][vi[k]]==1)) return 0;
for(int j=0;j<vi.size();j++) if(!vis[vi[j]])
{
for(int k=0;k<vi.size();k++) if(root(vi[j])==root(vi[k])&&j!=k) ans[vi[k]][vi[j]]=ans[vi[j]][vi[k]]=1,vis[vi[k]]=true;
vp.push_back(vi[j]),vis[vi[j]]=true;
}
for(int j=0;j<vp.size();j++) if(j==vp.size()-1) ans[vp[j]][vp[0]]=ans[vp[0]][vp[j]]=1;
else ans[vp[j]][vp[j+1]]=ans[vp[j+1]][vp[j]]=1;
}
}
build(ans);
return 1;
}
