#include "supertrees.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
int construct(std::vector<std::vector<int>> p) {
int N = p.size();
vector<vector<int>> ans(N, vector<int>(N));
vector<bool> flag(N);
auto tree = [&](vi v){
rep(i,1,v.size()){
ans[v[i-1]][v[i]] = ans[v[i]][v[i-1]] = 1;
}
rep(i,0,v.size()){
rep(j,i+1,v.size()){
if(p[v[i]][v[j]] != 1) return true;
}
}
return false;
};
auto loop = [&](vi v){
if(v.size() == 2) return true;
rep(i,0,v.size()){
ans[v[(i+1)%v.size()]][v[i]] = ans[v[i]][v[(i+1)%v.size()]] = 1;
}
rep(i,0,v.size()){
rep(j,i+1,v.size()){
if(p[v[i]][v[j]] != 2) return true;
}
}
return false;
};
vector<bool> mem_flag(N);
rep(i,0,N){
if(flag[i]) continue;
flag[i] = true;
std::queue<ll> que;
que.push(i);
vi v;
while(!que.empty()){
ll now = que.front(); que.pop();
v.pb(now);
rep(next, 0, N){
if(p[now][next]){
if(!flag[next]){
flag[next] = true;
que.push(next);
}
}
}
}
vi cnt(4);
for(auto el: v){
rep(j,0,N){
if(el == j) continue;
cnt[p[el][j]]++;
}
}
if(cnt[2] == 0){
if(tree(v)) return 0;
continue;
}
if(cnt[1] == 0){
if(loop(v)) return 0;
continue;
}
vector<pii> data;
for(auto el: v){
ll cnt = 0;
rep(j,0,N){
if(el == j) continue;
if(p[el][j] == 1) cnt++;
}
data.pb(mp(cnt, el));
}
sort(all(data));
reverse(all(data));
vi par;
vii member;
for(auto el: data){
if(mem_flag[el.second]) continue;
mem_flag[el.second] = true;
vi mb;
par.pb(el.second);
rep(j,0,N){
if(el.second == j) continue;
if(p[el.second][j] == 1){
mb.pb(j);
if(mem_flag[j]) return 0;
mem_flag[j] = true;
}
}
member.pb(mb);
}
if(par.size() <= 2) return 0;
rep(j,0,par.size()){
ans[par[j]][par[(j+1)%par.size()]] = ans[par[(j+1)%par.size()]][par[j]] = 1;
}
rep(j,0,par.size()){
for(auto el: member[j]) ans[par[j]][el] = ans[el][par[j]] = 1;
}
rep(j,0,par.size()){
rep(k,j+1,par.size()){
if(p[par[j]][par[k]] != 2) return 0;
for(auto el1: member[j]){
for(auto el2: member[k]){
if(p[el1][el2] != 2) return 0;
}
}
}
for(auto el1: member[j]){
for(auto el2: member[j]){
if(el1 == el2) continue;
if(p[el1][el2] != 1) return 0;
}
}
}
}
build(ans);
return 1;
}
