#include<bits/stdc++.h>
using namespace std;
void build(vector<vector<int>> b);
vector<vector<int>> Req;
vector<int> UF;
vector<vector<int>> Build;
int getTop(int a){
auto b=UF;
auto x=a;
if(UF[a]==a){
return a;
}
UF[a]=getTop(UF[a]);
return UF[a];
}
void join(int a,int b){
UF[getTop(b)]=getTop(a);
}
void connect(int i,int j){
Build[i][j]=1;
Build[j][i]=1;
}
int buildOneTree(vector<int> Tree){
for(int i=0;i<Tree.size();i++){
for(int j=i+1;j<Tree.size();j++){
if(Req[Tree[i]][Tree[j]]>1){
return 0;
}
}
}
for(int i=1;i<Tree.size();i++){
connect(Tree[i],Tree[0]);
}
return 1;
}
int BuildTree(vector<int> Tree){
int n=Tree.size();
UF=vector<int>(n);
for(int i=0;i<n;i++){
UF[i]=i;
}
int delta=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(Req[Tree[i]][Tree[j]]==0){
return 0;
}
if(Req[Tree[i]][Tree[j]]==1){
join(i,j);
}
if(Req[Tree[i]][Tree[j]]>1 && delta==0){
delta=Req[Tree[i]][Tree[j]];
}
if(Req[Tree[i]][Tree[j]]>1 && Req[Tree[i]][Tree[j]]!=delta){
return 0;
}
}
}
vector<vector<int>> SubTrees;
for(int i=0;i<n;i++){
if(UF[i]!=-1){
vector<int> NewTree;
int eq=UF[i];
for(int j=i;j<n;j++){
if(UF[j]==eq){
NewTree.push_back(Tree[j]);
UF[j]=-1;
}
}
SubTrees.push_back(NewTree);
}
}
if(delta<3){
if(SubTrees.size()==2){
return 0;
}
if(SubTrees.size()==1){
return buildOneTree(SubTrees[0]);
}
for(int i=0;i<SubTrees.size();i++){
if(buildOneTree(SubTrees[i])==0){
return 0;
}
connect(SubTrees[i][0],SubTrees[(i+1)%SubTrees.size()][0]);
}
return 1;
}
if(SubTrees.size()<3){
return 0;
}
connect(SubTrees[0][0],SubTrees[SubTrees.size()-1][0]);
connect(SubTrees[1][0],SubTrees[SubTrees.size()-1][0]);
if(buildOneTree(SubTrees[SubTrees.size()-1])==0){
return 0;
}
for(int i=0;i<SubTrees.size()-1;i++){
if(buildOneTree(SubTrees[i])==0){
return 0;
}
connect(SubTrees[i][0],SubTrees[(i+1)%(SubTrees.size()-1)][0]);
}
return 1;
};
int construct(vector<vector<int>> p){
Req=p;
int n=p.size();
Build=vector<vector<int>>(n,vector<int>(n));
UF=vector<int>(n);
for(int i=0;i<n;i++){
UF[i]=i;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]>0){
join(i,j);
}
}
}
vector<vector<int>> SubTrees;
for(int i=0;i<n;i++){
if(UF[i]!=-1){
vector<int> Tree;
int eq=UF[i];
for(int j=i;j<n;j++){
if(UF[j]==eq){
Tree.push_back(j);
UF[j]=-1;
}
}
SubTrees.push_back(Tree);
}
}
for(int i=0;i<SubTrees.size();i++){
if(BuildTree(SubTrees[i])==0){
return 0;
}
}
build(Build);
return 1;
}
