#include "supertrees.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define dbg(x) cout<<"?"<< #x <<" : "<<(x)<<endl; cout.flush();
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define all(x) (x).begin(), (x).end()
const int N = 1005;
struct Dsu{
int p[N];
V<int> v[N];
void reset(){
rep(i,0,N){
p[i] = -1;
v[i] = {i};
}
}
int find(int x){
if(p[x]==-1) return x;
return p[x] = find(p[x]);
}
bool same(int x,int y){
return find(x)==find(y);
}
void unite(int x,int y){
if((x=find(x))==(y=find(y))) return;
// wlog sz(x) > sz(y)
if(v[x].size() < v[y].size()) swap(x,y);
p[y] = x;
for(int i : v[y]) v[x].pb(i);
v[y].clear();
}
} dsu, t;
int n;
V<V<int>> ans, p;
void make_edge(int x,int y){
ans[x][y] = ans[y][x] = 1;
}
bool f(V<int>& v){
int sz = v.size();
bool two = false, tri = false;
for(int x : v) for(int y : v){
two |= p[x][y]==2;
tri |= p[x][y]==3;
}
if(two && tri) return false;
// straight path
if(!two && !tri){
rep(i,1,sz){
make_edge(v[i], v[i-1]);
}
return true;
}
// cycle grouping
for(int x : v) for(int y : v){
if(p[x][y] == 1){
t.unite(x,y);
}
}
// find main cycle
V<int> lead;
for(int x : v) if(t.find(x)==x){
lead.pb(x);
}
if(lead.size() <= 2) return false;
if(tri) return false;
//if(tri && lead.size()<=3) return false;
// make main cycle
rep(i,0,lead.size()){
make_edge(lead[i], lead[(i+1)%lead.size()]);
}
if(tri){
make_edge(lead[0], lead[2]);
}
// group of each nodes
for(int x : lead){
for(int y : t.v[x]) if(y != x){
make_edge(x, y);
}
}
return true;
}
int construct(V<V<int>> _p) {
p = _p; n = p.size();
dsu.reset(); t.reset();
ans = V<V<int>>(n,V<int>(n));
// connected components
rep(i,0,n) rep(j,0,i) if(p[i][j]){
dsu.unite(i,j);
}
rep(i,0,n) rep(j,0,i) if(dsu.same(i,j)){
if(p[i][j] == 0) return 0;
}
// solve per cc
rep(i,0,n) if(dsu.find(i) == i){
if(!f(dsu.v[i])) return 0;
}
build(ans);
return 1;
}
