#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se secod
#define sz(x) (int)x.size()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
using namespace std;
int n;
vector<int> par, sz;
int getpar(int x) {
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
bool same(int a, int b) {
return getpar(a)==getpar(b);
}
bool unite(int a, int b) {
a=getpar(a), b=getpar(b);
if (a==b) return 1;
if (sz[a]<sz[b]) swap(a, b);
sz[a]+=sz[b], par[b]=a;
return 1;
}
int construct(vector<vector<int>> base) {
n = sz(base);
par.resize(n), sz.resize(n, 1); iota(all(par), 0);
vector<vector<int>> answer(n, vector<int>(n, 0));
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (base[i][j] && !unite(i, j)) return 0;
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (!base[i][j] && same(i, j)) return 0;
}
}
vector<vector<int>> vec(n);
for (int i=0; i<n; i++) {
vec[getpar(i)].pb(i);
}
for (auto compo: vec) if (sz(compo)>1) {
int m=sz(compo);
vector<vector<int>> p(m, vector<int>(m));
for (int i=0; i<m; i++) {
for (int j=0; j<m; j++) {
p[i][j]=base[compo[i]][compo[j]];
}
}
vector<bool> used(m, 0);
int cnt=0;
for (int i=0; i<m; i++) if (!used[i]) {
vector<int> vec;
for (int j=0; j<m; j++) {
if (p[i][j]==1) vec.pb(j);
}
if (sz(vec)>1) {
for (auto &u: vec) used[u]=1;
for (int j=1; j<sz(vec); j++) {
answer[compo[vec[j-1]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[j-1]]]=1;
}
used[i]=0;
cnt++;
}
}
assert(cnt<=2);
vector<int> vec;
for (int i=0; i<m; i++) {
if (!used[i]) vec.pb(i);
}
if (sz(vec)==2) return 0;
assert(sz(vec)!=1);
for (int i=0; i<sz(vec); i++) {
answer[compo[vec[(i+1)%m]]][compo[vec[i]]]=answer[compo[vec[i]]][compo[vec[(i+1)%m]]]=1;
}
}
build(answer);
return 1;
}
