#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 1e3+5;
int n, dsu[nx], dsu2[nx];
vector<vector<int>> b;
vector<int> cycle[nx];
set<int> pa[nx];
int find(int x, int* d)
{
if(d[x] == x) return x;
d[x] = find(d[x], d);
return d[x];
}
void merge(int u, int v, int* d)
{
int pu = find(u, d), pv = find(v, d);
if(pu != pv)
d[pu] = pv;
}
int construct(vector<vector<int>> p)
{
n = p.size();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j] == 3) return 0;
iota(dsu, dsu + nx, 0);
iota(dsu2, dsu2 + nx, 0);
b.resize(n);
for(auto &row : b) row.resize(n);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if((p[i][j] == 1 || p[i][j] == 2) && i != j) merge(i, j, dsu2);
if(p[i][j] == 1 && i != j) merge(i, j, dsu);
}
}
// dsu2 -> connect the component together
// dsu -> connect only tree
for(int i=0;i<n;i++) {
bool in_cycle = false;
for(int j=0;j<n;j++) {
if(i != j && find(i, dsu) == find(j, dsu)) {
if(p[i][j] == 1 && find(i, dsu) != j) b[find(i, dsu)][j] = 1, b[j][find(i, dsu)] = 1;
if(p[i][j] == 0) return 0;
}
if(p[i][j] == 2 && i != j) in_cycle = true;
if(p[i][j] == 1 && i != j) in_cycle = false;
}
if(in_cycle) cycle[find(i, dsu2)].push_back(i);
}
for(int i=0;i<n;i++)
if(i != find(i, dsu))
pa[find(i, dsu2)].insert(find(i, dsu));
for(int i=0;i<n;i++) {
if(!cycle[i].empty() && !pa[i].empty()) {
// cout << "i : " << i << '\n';
// for(auto c : cycle[i]) cout << "cycle : " << c << '\n';
// for(int par : pa[i]) cout << "parent : " << par << '\n';
for(int par : pa[i]) cycle[i].push_back(par);
}
}
for(int i=0;i<n;i++) {
if(!cycle[i].empty()) {
for(int j=0;j<cycle[i].size();j++) {
int cur = cycle[i][j];
int nj = (j == cycle[i].size() - 1 ? 0 : j + 1);
int next = cycle[i][nj];
b[cur][next] = b[next][cur] = 1;
}
}
}
build(b);
return 1;
}
