#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e3+10;
struct UF{
int par[MAXM];
void init(int n){
for(int i=0;i<n;i++){
par[i] = i;
}
return;
}
int root(int x){
if(par[x]==x)return x;
else return par[x] = root(par[x]);
}
void mymerge(int a,int b){
a = root(a);
b = root(b);
par[b] = a;
return;
}
int getdiff(int a,int b){
if(root(a)^root(b))return 1;
else return 0;
}
}uf0,uf1;
vector<int> id[MAXM];
int construct(std::vector<std::vector<int>> p) {
int res = 1;
int n = p.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==3){
res = 0;
break;
}
}
if(!res)break;
}
if(!res)return 0;
uf0.init(n);
int a,b;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==1){
uf0.mymerge(i,j);
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]^1){
res&=uf0.getdiff(i,j);
}
}
}
if(!res)return 0;
uf1.init(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==2){
a = uf0.root(i);
b = uf0.root(j);
uf1.mymerge(a,b);
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==0){
res&=uf1.getdiff(uf0.root(i),uf0.root(j));
}
}
}
if(!res)return 0;
for(int i=0;i<n;i++){
a = uf0.root(i);
if(a^i)continue;
b = uf1.root(i);
id[b].push_back(i);
}
for(int i=0;i<n;i++){
if((int)id[i].size()==2){
res = 0;
break;
}
}
if(!res)return 0;
vector<vector<int> > answer(n);
for(int i=0;i<n;i++){
answer[i] = vector<int> (n,0);
}
for(int i=0;i<n;i++){
a = uf0.root(i);
if(a^i){
answer[i][a] = 1;
answer[a][i] = 1;
}
}
int cursz = 0;
for(int i=0;i<n;i++){
cursz = (int)id[i].size();
if(cursz>=3){
for(int j=0;j<cursz;j++){
answer[id[i][j]][id[i][(j+1)%cursz]] = 1;
answer[id[i][(j+1)%cursz]][id[i][j]] = 1;
}
}
}
build(answer);
return 1;
}
