#include <bits/stdc++.h>
#include "supertrees.h"
#define rall(s) s.end(), s.begin()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define pb push_back
#define vt vector
#define s second
#define f first
#define nl '\n'
using ll = long long;
//using pii = pair<int, int>;
//using pll = pair<ll, ll>;
using namespace std;
const int N = 1e5;
int pr[N], l[N];
int get(int x) {
if (pr[x] == x) return x;
return pr[x] = get(pr[x]);
}
void unite(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
if (l[a] > l[b]) swap(a, b);
pr[a] = b;
l[b] += l[a];
}
int construct(vt<vt<int>> p) {
int n = sz(p);
bool ok = 0;
vt<vt<int>> b;
for (int i = 0; i < n; i++) {
pr[i] = i, l[i] = 1;
}
for (int i = 0; i < n; i++) {
vt<int> s;
s.resize(n);
b.pb(s);
for (int j = i + 1; j < n; j++) {
if (p[i][j]) {
unite(i, j);
}
if (p[i][j] == 2) ok = 1;
}
}
vt<int> was(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (!p[i][j] && get(i) == get(j)) return 0;
}
if (was[i]) continue;
int x = get(i);
int lst = i;
was[i] = 1;
for (int j = i + 1; j < n; j++) {
if (get(j) == x) {
was[j] = 1;
b[lst][j] = b[j][lst] = 1;
lst = j;
}
}
if (ok && lst != i) {
if (b[i][lst] == 1) return 0;
b[lst][i] = b[i][lst] = 1;
}
}
build(b);
return 1;
}
