#include "supertrees.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 1000 + 7;
int t[N], sz[N];
int root(int x) {
if (t[x] == x) return x;
return t[x] = root(t[x]);
}
void join(int a, int b) {
a = root(a), b = root(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
t[b] = a;
sz[a] += sz[b];
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vi> sol(n, vi(n));
for (int i = 0; i < N; ++i) t[i] = i, sz[i] = 1;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] != 0) {
join(i, j);
if (p[i][j] == 3) return 0;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 0 && root(i) == root(j)) {
return 0;
}
}
}
auto add_edge = [&](int a, int b) -> void {
sol[a][b] = sol[b][a] = 1;
};
for (int i = 0; i < n; ++i) {
if (root(i) != i) continue;
vi cc;
for (int j = 0; j < n; ++j) if (root(j) == i) cc.push_back(j);
if (cc.size() == 1) {
continue;
}
vi vis(n, 0);
vector<int> chains;
for (auto x : cc) {
if (vis[x]) continue;
vi here;
here.push_back(x);
vis[x] = 1;
for (int j = 0; j < here.size(); ++j) {
for (auto k : cc) {
if (!vis[k] && p[here[j]][k] == 1) {
here.push_back(k);
vis[k] = 1;
}
}
}
for (auto x : here) {
for (auto y : here) {
if (x != y && p[x][y] == 2) return 0;
}
}
for (int j = 1; j < here.size(); ++j) add_edge(here[j - 1], here[j]);
chains.push_back(here.back());
}
if (chains.size() == 1) continue;
if (chains.size() == 2) return 0;
for (int j = 0; j < chains.size(); ++j) add_edge(chains[j], chains[(j + 1) % chains.size()]);
}
build(sol);
return 1;
}
