#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define R(i,n,...) for(int i=__VA_ARGS__+0; i<(n); ++i)
int construct(vector<vector<int>> A) {
const int N=A.size();
R(i, N) R(j, N) if(A[i][j]==3 || A[i][j]!=A[j][i]) return 0;
int M=0, K=0;
vector<int> X(N, -1), Y(N, -1);
vector<vector<int>> G(N), H(N), E(N, vector<int>(N));
function<void(int)> f1=[&](int i) {
G[X[i]=M].push_back(i);
R(j, N) if(A[i][j]==1 && !~X[j]) f1(j);
};
function<void(int)> f2=[&](int i) {
H[Y[i]=K].push_back(i);
R(j, N) if(A[i][j]==2 && !~Y[X[j]]) f2(X[j]);
};
auto con=[&](int i, int j) {
E[i][j]=E[j][i]=1;
};
R(i, N) if(!~X[i]) f1(i), M++;
R(i, M) if(!~Y[i]) f2(i), K++;
for(auto&v:G) {
const int L=v.size();
if(!L) continue;
for(int i:v) for(int j:v) if(A[i][j]!=1) return 0;
R(i, L, 1) con(v[i], v[i]-1);
}
for(auto&v:H) {
const int L=v.size();
if(L<=1) continue;
if(L==2) return 0;
for(int i:v) for(int j:v) if(i!=j) for(int k:G[i]) for(int l:G[j]) if(A[k][l]!=2) return 0;
R(i, L, 1) con(G[v[i]][0], G[v[i]-1][0]);
con(G[v[0]][0], G[v[L-1]][0]);
}
build(E);
return 1;
}
