#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
int construct(vector<vector<int>> p) {
int n = p.size();
vector<int> v;
vector<int> used(n);
function<void(int)> dfs = [&](int u){
v.push_back(u);
used[u] = 1;
for(int x=0;x<n;x++){
if(p[u][x] && !used[x]){
dfs(x);
}
}
};
vector<vector<int>> ans(n, vector<int>(n, 0));
for(int i=0;i<n;i++){
if(used[i]) continue;
dfs(i);
for(auto x : v){
for(auto y : v){
if(!p[x][y]){
return 0;
}
if(p[x][y] == 3){
return 0;
}
}
}
vector<int> c(n), one;
int last = 0;
function<void(int)> dfs = [&](int u){
one.push_back(u);
c[u] = last;
for(int x=0;x<n;x++){
if(!c[x] && p[u][x] == 1){
ans[u][x] = ans[x][u] = 1;
dfs(x);
}
}
};
vector<int> cyc;
for(auto u : v){
if(c[u]) continue;
last++;
dfs(u);
for(auto x : one){
for(auto y : one){
if(p[x][y] != 1) return 0;
}
}
cyc.push_back(u);
one.clear();
}
last = cyc.back();
for(auto x : cyc){
if(x != last) ans[x][last] = ans[last][x] = 1;
last = x;
}
v.clear();
}
build(ans);
return 1;
}
