#include "supertrees.h"
#include <vector>
#include <numeric>
using namespace std;
const int MAXN = 1e3;
int pa[MAXN];
int ra[MAXN];
void init() {
iota(pa, pa + MAXN, 0);
fill(ra, ra + MAXN, 0);
}
int get(int a) {
if (a == pa[a])
return a;
return pa[a] = get(pa[a]);
}
void merge(int a, int b) {
a = get(a);
b = get(b);
if (a == b)
return;
if (ra[b] > ra[a])
swap(a, b);
pa[b] = a;
if (ra[a] == ra[b])
ra[a]++;
}
vector<vector<int>> g;
vector<vector<int>> p2;
vector<int> comp;
vector<int> used;
int cur_time = 1;
void dfs(int v) {
used[v] = cur_time;
comp.push_back(v);
for (int u : g[v]) {
if (used[u] < cur_time) {
dfs(u);
}
}
}
int construct(vector<vector<int>> p) {
init();
int n = p.size();
used.resize(n);
g.resize(n);
p2.resize(n, vector<int> (n));
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3)
return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1) {
if (get(i) != get(j)) {
merge(i, j);
comp.clear();
dfs(i);
cur_time++;
auto c1 = comp;
comp.clear();
dfs(j);
cur_time++;
auto c2 = comp;
for (int el1 : c1) {
for (int el2 : c2) {
p2[el1][el2] = 1;
}
}
g[i].push_back(j);
g[j].push_back(i);
answer[i][j] = 1;
answer[j][i] = 1;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 2) {
}
}
}
for (int i = 0; i < n; i++) {
p2[i][i] = 1;
}
if (p != p2) {
return 0;
}
build(answer);
return 1;
}
