#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=2010, LOG=20;
vector<int> vec[MAXN];
vector<vector<int>> answer;
struct DSU{
int par[MAXN];
DSU(){
iota(par, par+MAXN, 0);
}
int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
void join(int x, int y){ par[get(x)]=get(y);}
} dsu1, dsu2;
inline void addedge(int u, int v){
answer[u][v]=answer[v][u]=1;
}
int construct(vector<vector<int>> A){
int n=A.size();
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i=0; i<n; i++) for (int j=0; j<n; j++){
if (A[i][j]>=1) dsu1.join(i, j);
if (A[i][j]==1) dsu2.join(i, j);
if (A[i][j]==3) return 0;
}
for (int i=0; i<n; i++) if (dsu2.par[i]==i) vec[dsu1.get(i)].pb(i);
for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (i!=j){
if (A[i][j]==0 && dsu1.get(i)==dsu1.get(j)) return 0;
if (A[i][j]>1 && dsu2.get(i)==dsu2.get(j)) return 0;
}
for (int i=0; i<n; i++) if (vec[i].size()>=2){
if (vec[i].size()==2) return 0; // :(
for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-1]);
addedge(vec[i][0], vec[i].back());
}
for (int i=0; i<n; i++) vec[i].clear();
for (int i=0; i<n; i++) vec[dsu2.get(i)].pb(i);
for (int i=0; i<n; i++) if (vec[i].size()>=2){
for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-1]);
}
build(answer);
return 1;
}
