#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 u == P[u] ? u : P[u] = find(P[u]);
};
function<bool(int , int)> same = [&](int u , int v){
return find(u) == find(v);
};
function<bool(int , int)> join = [&](int u , int 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);
for(int i = 0;i < n;i ++){
int c1 = 0 , c2 = 0;
for(int j = 0;j < n;j ++){
c1 += (p[i][j] == 1);
c2 += (p[i][j] == 2);
}
if(c1 == 1 && c2 == d.sz[d.find(i)] - 1){
cyc[d.find(i)].emplace_back(i);
}
}
for(int i = 0;i < n;i ++){
if(d.find(i) == i){
int c = (int)cyc[i].size() + (int)v[i].size();
if(c != d.sz[i]){
return 0;
}
if((int)v[i].size() > 0){
cyc[i].emplace_back(v[i][0]);
}
if((int)cyc[i].size() > 0){
for(int j = 0;j < (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 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;
}
}
}
build(ans);
return 1;
}
/*
int main(){
cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
}*/
