#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int n,N;
vvi p,c,g,G;
vi b,vis,ind;
void dfs(int v,int t){
vis[v]=1;
ind[v]=t;
b.push_back(v);
for(int i=0;i<n;i++) if(i!=v&&p[v][i]==1&&!vis[i]) dfs(i,t);
}
void DFS(int v){
vis[v]=1;
b.push_back(v);
for(int i=0;i<N;i++) if(i!=v&&G[v][i]==1&&!vis[i]) DFS(i);
}
int construct(vvi p_){
p=p_;
n=p.size();
vis=ind=vi(n);
g=vvi(n,vi(n));
int id=0;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(p[i][j]==3) return 0;
for(int i=0;i<n;i++) if(!vis[i]){
b.clear();
dfs(i,id);
int m=b.size();
for(auto v:b) for(auto u:b) if(p[u][v]!=1) return 0;
for(int j=1;j<m;j++){
int u=b[j-1],v=b[j];
g[u][v]=g[v][u]=1;
}
id++;
c.push_back(b);
}
N=c.size();
G=vvi(N,vi(N));
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j]==2){
int u=ind[i],v=ind[j];
G[u][v]=G[v][u]=1;
}
vis=vi(N);
for(int i=0;i<N;i++) if(!vis[i]){
b.clear();
DFS(i);
int m=b.size();
for(auto I:b) for(auto J:b) if(I<J){
for(auto u:c[I]) for(auto v:c[J]) if(p[u][v]!=2) return 0;
}
if(m==1) continue;
if(m==2) return 0;
for(int j=0;j<m;j++){
int u=c[b[j]][0],v=c[b[(j+1)%m]][0];
g[u][v]=g[v][u]=1;
}
}
build(g);
return 1;
}
