#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1e3;
struct DSU{
vector<int> par, sz, trace;
int cnt;
inline DSU(int n){
par.resize(n);
sz.resize(n, 1);
for (int i = 0; i < n; ++i) par[i] = i;
trace.resize(n, -1);
cnt = -1;
}
inline int find(int x){
return (par[x] == x) ? x : (par[x] = find(par[x]));
}
inline void merge(int x, int y){
int u = find(x), v = find(y);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return;
}
inline int order(int x){
int u = find(x);
if (trace[u] == -1)
trace[u] = ++cnt;
return trace[u];
}
};
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> vec(n);
vector<vector<int>> a (n, vector<int> (n, 0));
DSU dsu(n);
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j) if (j != i){
if (p[i][j] != 0) dsu.merge(i, j);
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j)if (i != j){
if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
return 0;
}
}
for (int i = 0; i < n; ++i)
vec[dsu.order(i)].push_back(i);
int cnt = dsu.cnt;
for (int k = 0; k < cnt; ++k){
vector<int>& v = vec[k];
for (int i = 0; i < v.size() - 1; ++i)
a[v[i]][v[i + 1]] = a[v[i + 1]][v[i]] = 1;
}
build(a);
return 1;
}
