#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>>adj;
int pa[1005];
int fp(int a){return pa[a]==a?a:pa[a]=fp(pa[a]);}
void un(int a,int b){pa[fp(b)]=fp(a);}
int have1[1005];
int have2[1005];
int have3[1005];
int vis1[1005];
int vis2[1005];
int vis3[1005];
int cant=0;
vector<vector<int>> answer;
void build1(int u){
//cerr<<"build1:"<<u<<"\n";
vector<int>node;
node.push_back(u);
vis1[u]=1;
for(int i=0;i<N;i++)if(i!=u&&adj[u][i]==1){
vis1[i]=1;
node.push_back(i);
un(i,u);
}
//for(auto x:node)cerr<<x<<" ";
//cerr<<"\n";
for(int i=0;i<node.size()-1;i++){
int x=node[i],y=node[i+1];
answer[x][y]=1,answer[y][x]=1;
}
}
void build2(int u){
//cerr<<"build2:"<<u<<"\n";
vector<int>node;
node.push_back(u);
vis2[u]=1;
for(int i=0;i<N;i++){
int x=fp(i);
if(vis2[x])continue;
if(x!=u&&adj[u][x]==2){
vis2[x]=1;
node.push_back(x);
}
}
if(node.size()<3)cant=1;
for(int i=0;i<node.size();i++){
int x=node[i],y=node[(i+1)%node.size()];
answer[x][y]=1,answer[y][x]=1;
}
}
void build3(int u){
vector<int>node;
node.push_back(u);
vis3[u]=1;
if(vis2[u])cant=1;
for(int i=0;i<N;i++){
int x=fp(i);
if(vis3[x])continue;
if(x!=u&&adj[u][x]==3){
vis3[x]=1;
node.push_back(x);
if(vis2[x])cant=1;
}
}
if(node.size()<4){
cant=1;
return;
}
for(int i=0;i<node.size();i++){
int x=node[i],y=node[(i+1)%node.size()];
answer[x][y]=1,answer[y][x]=1;
}
answer[node[0]][node[2]]=answer[node[2]][node[0]]=1;
}
void check_con(){
for(int i=0;i<N;i++)pa[i]=i;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(adj[i][j]>0)un(i,j);
}
}
for(int i=0;i<N;i++)for(int j=0;j<N;j++){
if(i==j)continue;
int x=(adj[i][j]>0);
int y=(fp(i)==fp(j));
if(x!=y)cant=1;
}
}
int construct(std::vector<std::vector<int>> p) {
N = p.size();
for (int i = 0; i < N; i++) {
vector<int> row;
row.resize(N);
answer.push_back(row);
}
adj=p;
for(int i=0;i<N;i++)pa[i]=i;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int x=p[i][j];
if(x==1)have1[i]=1;
else if(x==2)have2[i]=1;
else if(x==3)have3[i]=1;
if(have2[i]&&have3[i])cant=1;
}
}
for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(adj[i][j]!=adj[j][i]||(i==j&&adj[i][j]!=1))cant=1;
for(int i=0;i<N;i++)if(have1[i]&&vis1[i]==0)build1(i);
for(int i=0;i<N;i++){
int x=fp(i);
if(have2[x]&&vis2[x]==0)build2(x);
}
for(int i=0;i<N;i++){
int x=fp(i);
if(have3[x]&&vis3[x]==0)build3(x);
}
check_con();
if(cant)return 0;
build(answer);
return 1;
}
