#include <bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#include <vector>
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> ans (n, vector < int > (n));
vector < array < bool, 3 > > pt (n);
vector < pair < int, int > > dsu (n);
set < int > r;
for (int i = 0; i < n; ++i) dsu[i].first = -1, dsu[i].second = 1;
auto dsuc = [&] (int x)
{
while (dsu[x].first != -1) x = dsu[x].first;
return x;
};
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (p[i][j])
{
if (p[i][j] == 3) return 0;
pt[i][p[i][j]] = pt[j][p[i][j]] = true;
if (p[i][j] == 1 && !r.count (i) && !r.count (j))
ans[i][j] = 1, ans[j][i] = 1, r.insert (j);
int ci = dsuc (i), cj = dsuc (j);
if (ci != cj)
{
if (dsu[ci].second < dsu[cj].second) swap (ci, cj);
dsu[cj].first = ci;
dsu[ci].second += dsu[cj].second;
}
}
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (!p[i][j] && dsuc (i) == dsuc (j)) return 0;
map < int, array < set < int >, 3 > > m;
for (int i = 0; i < n; ++i)
{
int ci = dsuc (i);
if (pt[i][1]) m[ci][1].insert (i);
if (pt[i][2]) m[ci][2].insert (i);
}
for (auto &[xx, x] : m)
{
if (x[2].empty ()) continue;
if (x[2].size () <= 2) return 0;
int pr = *prev (x[2].end ());
for (auto &y : x[2])
{
if (r.count (y)) continue;
ans[pr][y] = ans[y][pr] = 1;
pr = y;
for (int i = 0; i < n; ++i)
if (i != y && x[1].count (i) && p[y][i] == 1)
ans[i][y] = ans[y][i] = 1;
}
}
build (ans);
return 1;
}
