#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU
{
vector<int> e;
void init(int n)
{
e.assign(n, -1);
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
int unite(int x, int y)
{
x = get(x), y = get(y);
if (x == y) return 0;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int> (n, 0));
DSU dsu;
dsu.init(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (p[i][j] == 3) return 0;
if (p[i][j] == 1 && dsu.unite(i, j)) ans[i][j] = ans[j][i] = 1;
}
}
vector<int> comp[n];
for (int i = 0; i < n; i++) comp[dsu.get(i)].push_back(i);
DSU d1;
d1.init(n);
for (int i = 0; i < n; i++)
{
if (i != dsu.get(i)) continue;
for (int &j : comp[i])
{
for (int k = 0; k < n; k++)
{
if ((p[j][k] == 2) != (p[i][k] == 2)) return 0;
}
}
for (int j = 0; j < n; j++)
{
if (p[i][j] == 2) d1.unite(i, dsu.get(j));
}
}
vector<int> con[n];
for (int i = 0; i < n; i++) con[d1.get(i)].push_back(i);
for (int i = 0; i < n; i++)
{
if (con[i].size() <= 1) continue;
if (con[i].size() == 2) return 0;
int prev = con[i].back();
for (int &j : con[i])
{
ans[prev][j] = ans[j][prev] = 1;
prev = j;
}
}
build(ans);
return 1;
}
