#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 5;
void build(std::vector<std::vector<int>> _b) ;
vector<int> sn0[N] , sn1[N];
int fa0[N] , fa1[N];
vector<int> f;
void unit0(int v , int u){
v = fa0[v] , u = fa0[u];
if(v == u) return ;
if(sn0[v].size() < sn0[u].size()) swap(u , v);
sn1[u].clear();
while(sn0[u].size()){
sn0[v].push_back(sn0[u].back());
fa0[sn0[u].back()] = v;
sn0[u].pop_back();
}
}
void unit1(int v , int u){
v = fa1[v] , u = fa1[u];
if(v == u) return ;
if(sn1[v].size() < sn1[u].size()) swap(u , v);
while(sn1[u].size()){
sn1[v].push_back(sn1[u].back());
fa1[sn1[u].back()] = v;
sn1[u].pop_back();
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer(n , vector<int> (n , 0));
f = vector<int> (n , 1);
for(int i = 0;i < n; ++ i){
fa0[i] = fa1[i] = i;
sn0[i] = sn1[i] = {i};
}
for(int i = 0;i < n; ++ i){
for(int j = 0;j < n; ++ j){
if(p[i][j] == 1){
unit0(i , j);
}
if(p[i][j] == 3) return 0;
}
}
for(int i = 0;i < n; ++ i){
for(auto to : sn0[i]){
if(to == i) continue ;
answer[to][i] = 1;
answer[i][to] = 1;
//cout << to << ' ' << i << '\n';
}
}
//cout << "end\n\n";
for(int i = 0;i < n; ++ i){
for(int j = 0;j < n; ++ j){
if(p[i][j] > 1){
unit1(fa0[i] , fa0[j]);
}
}
}
for(int i = 0;i < n; ++ i){
if(sn1[i].size() == 0) continue ;
int sz = sn1[i].size() , k = 1;
if(sz > 1){
k = p[sn1[i][0]][sn1[i][1]];
}
for(int j = 0;j < sz - 1; ++ j){
//cout << sn1[i][j] << ' ' << sn1[i][j + 1] << '\n';
answer[sn1[i][j]][sn1[i][j + 1]] = 1;
answer[sn1[i][j + 1]][sn1[i][j]] = 1;
}
f[i] = k;
if(k > 1){
k --;
if(sz > 2){
answer[sn1[i][0]][sn1[i][sz - 1]] = 1;
answer[sn1[i][sz - 1]][sn1[i][0]] = 1;
}
else return 0;
}
}
bool ok = true;
for(int i = 0;i < n;++ i){
for(int j = 0;j < n; ++ j){
int cnt = 0;
if(fa0[i] == fa0[j]) cnt = 1;
else if(fa1[fa0[i]] == fa1[fa0[j]]){
cnt = f[fa1[fa0[i]]];
}
ok &= (p[i][j] == cnt);
}
}
if(ok) build(answer);
return ok;
}
