#include "supertrees.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
struct dsu{
int n , cnt;
vector<int> P , sz;
dsu(int _size){
n = _size;
cnt = _size;
P = vector<int>(_size + 1);
iota(P.begin() , P.end() , 0);
sz = vector<int>(_size + 1);
fill(sz.begin() , sz.end() , 1);
}
function<int(int)> Find = [&](int u){
return find(u) - 1;
};
function<int(int)> find = [&](int u){
return u == P[u] ? u : (P[u] = find(P[u]));
};
function<bool(int , int)> same = [&](int u , int v){
++u,++v;
return find(u) == find(v);
};
function<bool(int , int)> join = [&](int u , int v){
++u,++v;
u = find(u);
v = find(v);
if(u != v){
if(sz[u] < sz[v]){
swap(u , v);
}
P[v] = u;
sz[u] += sz[v];
--cnt;
return true;
}
return false;
};
};
int construct(std::vector<std::vector<int>> p) {
int n = (int)p.size();
dsu d(n);
for(int i = 0;i < n;i ++){
for(int j = 0;j < n;j ++){
if(p[i][j] > 0){
d.join(i , j);
}
}
}
for(int i = 0;i < n;i ++){
for(int j = 0;j < n;j ++){
if(d.same(i , j) && !p[i][j]){
return 0;
}
}
}
dsu dx(n);
for(int i = 0;i < n;i ++){
for(int j = 0;j < n;j ++){
if(p[i][j] == 1){
dx.join(i , j);
}
}
}
for(int i = 0;i < n;i ++){
for(int j = 0;j < n;j ++){
if(dx.same(i , j) && p[i][j] != 1){
return 0;
}
}
}
vector<vector<int>> ans(n , vector<int>(n));
vector<vector<int>> v(n);
for(int i = 0;i < n;i ++){
v[dx.Find(i)].emplace_back(i);
}
for(int i = 0;i < n;i ++){
for(int j = 0;j + 1 < (int)v[i].size();j ++){
ans[v[i][j]][v[i][j + 1]] = 1;
ans[v[i][j + 1]][v[i][j]] = 1;
}
}
vector<int> st(n);
vector<vector<int>> cyc(n) , w(n);
for(int i = 0;i < n;i ++){
w[dx.Find(i)].emplace_back(i);
if(dx.Find(i) == i){
cyc[d.Find(i)].emplace_back(i);
}
}
for(int i = 0;i < n;i ++){
if(d.Find(i) == i){
if((int)cyc[i].size() == 2){
return 0;
}
for(int j = 0;j + 1 < (int)cyc[i].size();j ++){
int e = (j + 1) % ((int)cyc[i].size());
ans[cyc[i][j]][cyc[i][e]] = 1;
ans[cyc[i][e]][cyc[i][j]] = 1;
}
for(int x : cyc[i]){
for(int a : w[x]){
for(int j = 0;j < n;j ++){
if(d.Find(j) == i && dx.Find(j) != x){
if(p[a][j] != 2){
return 0;
}
}
}
}
}
}
}
build(ans);
return 1;
}
