#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int par[1005], inTree[1005];
vector<int> cyc[1005], tree[1005];
int qry(int x) { return x == par[x] ? x : par[x] = qry(par[x]); }
void join(int x, int y) { par[qry(x)] = qry(y); }
int construct(vector<vector<int>> p) {
auto check_connectivity = [&](int n) {
iota(par, par+n, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] != 0)
join(i, j);
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (p[i][j] == 0 && qry(i) == qry(j))
return 0;
return 1;
};
auto connect = [&](int n, int t) {
iota(par, par+n, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == t)
join(i, j);
};
int n = p.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] > 2 || p[i][j] != p[j][i])
return 0;
if (!check_connectivity(n))
return 0;
connect(n, 2);
for (int i = 0; i < n; i++)
cyc[qry(i)].push_back(i);
connect(n, 1);
for (int i = 0; i < n; i++)
tree[qry(i)].push_back(i);
vector<vector<int>> ans(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
if (int(tree[i].size()) <= 1)
continue;
int l = -1;
for (int j: tree[i]) {
for (int k: tree[i])
if (p[j][k] != 1)
return 0;
if (l != -1)
ans[l][j] = ans[j][l] = 1;
l = j, inTree[j] = 1;
}
}
for (int i = 0; i < n; i++) {
if (int(cyc[i].size()) <= 1)
continue;
vector<int> nx;
for (int j: cyc[i]) {
if (!inTree[j])
nx.push_back(j);
else if (qry(j) == j)
nx.push_back(j);
}
if (int(nx.size()) <= 2)
return 0;
int l = -1;
for (int j: nx) {
if (l != -1)
ans[l][j] = ans[j][l] = 1;
l = j;
}
ans[l][nx[0]] = ans[nx[0]][l] = 1;
}
build(ans);
return 1;
}
