#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
vector<pii> c1;
vector<pii> c2;
vector<int> c3;
vector<vector<int> > P;
int N;
int r[1010][4];
vector<vector<int>> B;
void b1(){
for(int i=0; i<N; i++){
if(r[i][1]==(-1)){
r[i][1]=i;
int mx=i;
for(int j=0; j<N; j++){
if( (P[i][j]==1) && (i!=j) ){
B[mx][j]=1;
B[j][mx]=1;
r[j][1]=i;
mx=j;
}
}
c1.pb({i, mx});
}
}
}
void b2(){
for(pii p1:c1){
int u1=p1.ft, v1=p1.sc;
if(r[u1][2]==(-1)){
c2.pb({u1, u1});
r[u1][2]=u1;
int mx=u1;
for(pii p2:c1){
int u2=p2.ft, v2=p2.sc;
if(u2==u1){continue;}
if( (r[u2 ][2]==(-1)) && (P[mx][u2]==2) ){
B[mx][u2]=1;
B[u2][mx]=1;
r[u2][2]=u1;
mx=u2;
c2.back()={v1, v2};
}
}
if( (c2[c2.size()-1])==mp(u1, u1) ){
c2.pop_back();
}
else{
B[u1][mx]=1;
B[mx][u1]=1;
}
}
}
}
bool check(){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(P[i][j]==3){
return false;
}
if( (r[i][1]==r[j][1]) && (P[i][j]!=1) ){
return false;
}
if( (r[i][1]!=r[j][1]) && (P[i][j]==1) ){
return false;
}
if( (P[i][j]==2) && ( (r[ r[i][1] ][2]!=r[ r[j][1] ][2]) || (r[ r[i][1] ][2]==(-1)) || (r[i][1]==r[j][1]) ) ){
return false;
}
if( (r[ r[i][1] ][2]==r[ r[j][1] ][2]) && (r[ r[i][1] ][2]!=(-1)) && (r[i][1]!=r[j][1]) && (P[i][j]!=2) ){
return false;
}
if( (P[i][j]==0) && ( ( (r[r[i][1] ][2]==r[r[j][1] ][2]) && (r[r[i][1] ][2]!=(-1)) ) || (r[i][1]==r[j][1] ) ) ){
return false;
}
if( (P[i][j]!=0) && ( ( (r[r[i][1] ][2]==(-1)) || (r[r[i][1] ][2]!=r[r[j][1] ][2]) ) && ( r[i][1]!=r[j][1] ) ) ){
return false;
}
}
}
return true;
}
int construct(std::vector<std::vector<int>> p) {
P=p; N=P.size();
memset(r, -1, sizeof(r));
B.resize(N);
for(int i=0; i<N; i++){
B[i].resize(N);
for(int j=0; j<N; j++){
B[i][j]=0;
}
}
b1();
b2();
if(check()){
build(B);
return 1;
}
return 0;
}
