#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct DSU {
vector<int> rank, parent;
DSU(int n) {
rank.assign(n, 1);
parent.resize(n);
for (int i=0; i<n; i++) {
parent[i] = i;
}
}
int find(int n) {
return (n == parent[n] ? n : parent[n] = find(parent[n]));
}
void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
if (p1 == p2) return;
rank[p1] += rank[p2];
parent[p2] = p1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n, 0));
bool can = true;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] != p[j][i]) can = false;
}
}
if (!can) {
return 0;
}
DSU dsu(n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] >= 1) dsu.unite(i, j);
}
}
for (int i=0; i<n; i++) {
int pi = dsu.find(i);
if (pi == i) {
//i es el root de su componente
vector<int> cmp;
for (int j=0; j<n; j++) {
int pj = dsu.find(j);
if (pi==pj) {
cmp.push_back(j);
}
}
//cmp tiene la componente completa
vector<int> star; //Nodos en star son aquellos que deben formar una estrella;
set<int> s;
for (auto x : cmp) {
for (auto y : cmp) {
if (x==y) continue;
if (p[x][y] == 1) {
s.insert(x);
s.insert(y);
}
}
}
star = vector<int>(s.begin(), s.end());
if (star.size()>0) {
int u = star[0];
for (auto x : star) {
ans[u][x] = ans[x][u] = 1;
}
//Formo estrella
}
vector<int> complement;
for (auto x : cmp) {
if (!s.count(x)) complement.push_back(x);
}
//Complement son aquellos nodos que estan en la componente pero no deben ser parte de la estrella.
//Si hay estrella en la componente, uno de estos nodos debe estar conectado al ciclo.
//Otherwise, el ciclo es toda la componente
if (star.size()>0) complement.push_back(star[0]);
int m = complement.size();
for (int j=0; j<m; j++) {
int u = complement[j];
int v = complement[(j+1)%m];
ans[u][v] = ans[v][u] = 1;
}
for (auto x : cmp) {
for (auto y : cmp) {
if (p[x][y] == 0) return 0;
}
}
if (star.size()==0 && cmp.size()==2) return 0;
}
}
for (int i=0; i<n; i++) {
ans[i][i] = 0;
}
build(ans);
return 1;
}
