#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define endl "\n"
typedef long long ll;
struct DSU {
int n;
vector<int> link, sz;
DSU(int n) : n(n), link(n), sz(n, 1) {
iota(all(link), 0);
}
int find(int x) {
return link[x] == x ? x : link[x] = find(link[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x, y);
link[y] = x;
sz[x] += sz[y];
return true;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n));
DSU dsu1(n), dsu2(n);
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (p[i][j] == 1)
if (dsu1.unite(i, j))
ans[i][j] = 1, ans[j][i] = 1;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (p[i][j] == 2)
dsu2.unite(dsu1.find(i), dsu1.find(j));
for (int i = 0; i < n; i++) {
int p = -1;
int f = -1;
for (int j = 0; j < n; j++)
if (dsu2.find(j) == i) {
if (f == -1)
f = j;
if (p != -1)
ans[j][p] = 1, ans[p][j] = 1;
p = j;
}
if (f != p)
ans[f][p] = 1, ans[p][f] = 1;
}
for (int i = 0; i < n; i++)
if (p[i][i] != 1)
return 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++) {
if (p[i][j] == 0 and (dsu1.find(i) == dsu1.find(j) or dsu2.find(dsu1.find(i)) == dsu2.find(dsu1.find(j))))
return 0;
if (p[i][j] == 1 and dsu1.find(i) != dsu1.find(j))
return 0;
if (p[i][j] == 2 and (dsu1.find(i) == dsu1.find(j) or dsu2.find(dsu1.find(i)) != dsu2.find(dsu1.find(j))))
return 0;
if (p[i][j] == 3)
return 0;
}
build(ans);
return 1;
}
