#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1005;
#define sz(x) (int)(x.size())
int par_p[MX],par_s[MX];
vector<int> bucket[MX];
bitset<MX> vis;
int find_p(int i){
if(par_p[i]==i)return i;
return par_p[i]=find_p(par_p[i]);
}
int find_s(int i){
if(par_s[i]==i)return i;
return par_s[i]=find_s(par_s[i]);
}
void Union_s(int i,int j){
i=find_s(i),j=find_s(j);
if(i!=j)par_s[i]=j;
}
void Union_p(int i,int j){
i=find_p(i),j=find_p(j);
if(i!=j)par_p[i]=j;
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if(p[i][j]==3)return 0;
vector<vector<int> > ans(n);
for (int i = 0; i < n; ++i){
par_p[i]=par_s[i]=i;
ans[i].resize(n);
}
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
{
if(p[i][j]==2)
Union_s(i,j);
else if(p[i][j]==1)Union_p(i,j);
}
for (int i = 0; i < n; ++i)
if(!vis[find_p(i)]){
vis[find_p(i)]=1;
bucket[find_s(i)].push_back(find_p(i));
}
for (int i = 0; i < n; ++i)
{
//cerr<<sz(bucket[i])<<"-";
if(sz(bucket[i])==2)return 0;
if(sz(bucket[i])<=1)continue;
for (int j = 0; j < sz(bucket[i]); ++j)
ans[bucket[i][j]][bucket[i][(j+1)%sz(bucket[i])]]=ans[bucket[i][(j+1)%sz(bucket[i])]][bucket[i][j]]=1;
}
for (int i = 0; i < n; ++i)
if(find_p(i)!=i)ans[find_p(i)][i]=ans[i][find_p(i)]=1;
for (int i = 0; i < n; ++i)
{
for (int j = i+1; j < n; ++j)
{
//cerr<<p[i][j]<<" ";
if((p[i][j]==0) && (find_s(find_p(i))==find_s(find_p(j))))return 0;
if((p[i][j]==2) && ((find_p(i)==find_p(j))|| (find_s(find_p(i))!=find_s(find_p(j)))))return 0;
if((p[i][j]==1) && (find_p(i)!=find_p(j)))return 0;
}
}
build(ans);
return 1;
}
