#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define sz(x) (int)(x).size()
#define pb push_back
struct DSU{
vi e;
void init(int n){
e = vi(n, -1);
}
int get(int a){
if(e[a] < 0) return a;
e[a] = get(e[a]);
return e[a];
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return 0;
if(-e[a] < -e[b]) swap(a, b);
e[a]+=e[b];
e[b] = a;
return 1;
}
};
const int mx = 1005;
int n;
vector<vi> p;
vector<vi> ans;
vi comps[mx];
vi lins[mx];
bool solve(vi comp){ //solve in sz(comp)*n time
assert(sz(comp) > 0);
vi incomp(n, 0);
for(auto u: comp){
incomp[u] = 1;
}
for(auto u: comp){
for(int i = 0; i < n; i++){
if(incomp[i] == 1){
if(p[u][i] == 0) return 0; //component is not connected to anything
}
else{
assert(p[u][i] == 0);
}
}
}
DSU dsu2;
dsu2.init(sz(comp));
vector<vi> subcomps(sz(comp), vi{});
for(int i = 0; i < sz(comp); i++){
for(int j = i+1; j < sz(comp); j++){
if(p[comp[i]][comp[j]] == 1){
dsu2.unite(i, j);
}
}
}
for(int i = 0; i < sz(comp); i++){
subcomps[dsu2.get(i)].pb(i);
}
vi cyc;
for(int i = 0; i < sz(comp); i++){
if(sz(subcomps[i]) == 0) continue;
vi insub(sz(comp), 0);
for(auto u: subcomps[i]){
insub[u] = 1;
}
for(auto u: subcomps[i]){
for(int j = 0; j < sz(comp); j++){
if(insub[j] == 1){
if(p[comp[u]][comp[j]] != 1) return 0;
}
else{
if(p[comp[u]][comp[j]] != 2) return 0;
}
}
}
for(int j = 0; j+1 < sz(subcomps[i]); j++){
int a = comp[subcomps[i][j]];
int b = comp[subcomps[i][j+1]];
ans[a][b] = 1;
ans[b][a] = 1;
}
cyc.pb(comp[subcomps[i][0]]);
}
if(sz(cyc) >= 2){
for(int i = 0; i < sz(cyc); i++){
int a = cyc[i];
int b = cyc[(i+1) % sz(cyc)];
assert(a != b);
ans[a][b] = 1;
ans[b][a] = 1;
}
}
bool SUB3 = 1;
for(auto u1: comp){
for(auto u2: comp){
assert(p[u1][u2] != 0);
if(p[u1][u2] != 2) SUB3 = 0;
}
}
if(SUB3){
vi incomp(n, 0);
for(auto u: comp) incomp[u] = 1;
for(auto u: comp){
for(int i = 0; i < n; i++){
if(incomp[i] == 0){
assert(p[u][i] == 0);
}
else{
assert(p[u][i] == 2);
}
}
}
}
return 1;
}
int construct(vector<vi> _p) {
p = _p;
_p.clear();
n = sz(p);
for(int i = 0; i < n; i++){
if(p[i][i] != 1) return 0;
for(int j = 0; j < n; j++){
if(p[i][j] != p[j][i]) return 0;
if(p[i][j] == 3) return 0;
}
}
for(int i = 0; i < n; i++) {
vi row(n, 0);
ans.pb(row);
}
DSU dsu0;
dsu0.init(n);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j] > 0){
dsu0.unite(i, j);
}
}
}
for(int i = 0; i < n; i++){
comps[dsu0.get(i)].pb(i);
}
for(int i = 0; i < n; i++){
if(sz(comps[i]) == 0) continue;
int res = solve(comps[i]);
if(res == 0) return 0;
}
build(ans);
return 1;
}
