#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using vvi = vector<vector<int>>;
struct DSU {
vi p, sz;
int n, compo;
void init(int _n) {
n = _n;
compo = n;
p.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) p[i] = i;
}
int getpar(int x) {
if (p[x] != x) p[x] = getpar(p[x]);
return p[x];
}
void connect(int x, int y) {
int a = getpar(x);
int b = getpar(y);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
bool same(int x, int y) {
return getpar(x) == getpar(y);
}
};
vvi g;
int construct(vvi p) {
int n = p.size();
g.resize(n, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
int cnt2 = 0, cnt3 = 0;
for (int j = 0; j < n; j++) {
if (p[i][j] == 2) cnt2++;
if (p[i][j] == 3) cnt3++;
}
// if (cnt2 == 1 || (cnt3 && cnt3 <= 2)) return 0;
// if (cnt2 > 0 && cnt3 > 0) return 0;
vector<int> nodes;
for (int j = 0; j < n; j++) {
if ((p[i][j] == 0 && g[i][j] == 1) || (g[i][j] != -1)) return 0;
if (p[i][j] == 0 || i == j) continue;
if (p[i][j] == 1) {
g[i][j] = 1;
g[j][i] = 1;
continue;
}
nodes.push_back(j);
}
if (nodes.empty()) continue;
for (auto to : nodes) {
if (g[i][to] != -1) continue;
g[i][to] = 1;
g[to][i] = 1;
}
for (int j = 1; j < isz(nodes); j++) {
if (g[nodes[j]][nodes[j - 1]] != -1) continue;
g[nodes[j]][nodes[j - 1]] = 1;
g[nodes[j - 1]][nodes[j]] = 1;
}
for (int j = 0; j < n; j++) {
if (p[i][j] < 2) continue;
if (count(all(nodes), j) == 0) {
g[nodes.back()][j] = 1;
g[j][nodes.back()] = 1;
}
}
}
build(g);
return 1;
}
