#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
struct dsu {
vector<int> p, sz;
dsu(int n) : p(n), sz(n) {
iota(all(p), 0);
}
int find(int v) {
return v == p[v] ? v : p[v] = find(p[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
dsu d(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j]) {
d.unite(i, j);
}
}
}
vector<vector<int>> v(n);
vector<vector<int>> b(n, vector<int>(n));
for(int i = 0; i < n; i++) {
v[d.find(i)].pb(i);
}
for(int i = 0; i < n; i++) {
auto &u = v[i];
set<int> st;
for(int j = 0; j < (int)u.size(); j++) {
for(int k = 0; k < (int)u.size(); k++) {
if( u[j] == u[k] ) continue;
if( p[ u[j] ][ u[k] ] == 1 ) {
b[ u[j] ][ u[k] ] = 1;
} else if( p[ u[j] ][ u[k] ] == 2 ) {
st.emplace(u[j]);
st.emplace(u[k]);
}
}
}
if(!st.empty()) {
assert(st.size() > 2);
int last = *(--st.end());
for(auto j : st) {
b[j][last] = b[last][j] = 1;
last = j;
}
}
}
build(b);
return true;
}
