#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define pb push_back
#define sz size()
const int N = 1005;
int a[N][N], a1, par[N], par1[N];
vector <int> q;
vector<vector<int>> answer;
int get (int x) {
if (x == par[x]) return x;
return par[x] = get (par[x]);
}
void uni (int x, int y) {
x = get (x);
y = get (y);
par[max (x, y)] = min(x, y);
}
int get1 (int x) {
if (x == par1[x]) return x;
return par1[x] = get1 (par1[x]);
}
void uni1 (int x, int y) {
x = get1 (x);
y = get1 (y);
par1[max (x, y)] = min (x, y);
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; ++i) {
par[i] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
assert (p[i][j] == p[j][i]);
if (i == j) continue;
if (p[i][j] == 3) return 0;
if (p[i][j]) {
uni (i, j);
}
a1 = max (a1, p[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
if (!p[i][j] and get(i) == get(j)) return 0;
}
}
for (int i = 0; i < n; ++i) {
q.clear();
for (int j = 0; j < n; ++j) {
if (get(j) == i) q.pb (j);
}
if ((int)q.sz == 0) continue;
for (int i = 0; i < n; ++i) par1[i] = i;
for (int ii = 0; ii < (int)q.sz; ++ii) {
for (int jj = 0; jj < (int)q.sz; ++jj) {
if (ii == jj) continue;
if (p[q[ii]][q[jj]] == 1) {
uni1(ii, jj);
}
}
}
vector <vector <int>> g((int)q.sz);
for (int j = 0; j < (int)q.sz; ++j) {
g[get1(j)].pb (q[j]);
}
vector <int> h;
for (int j = 0; j < (int)g.sz; ++j) {
if ((int)g[j].sz) {
h.pb (g[j][0]);
}
for (int k = 0; k + 1< (int)g[j].sz; ++k) {
a[g[j][k]][g[j][k + 1]] = 1;
a[g[j][k + 1]][g[j][k]] = 1;
}
}
if ((int)h.sz == 2 and a1 == 2) return 0;
if ((int)h.sz > 2 and a1 == 2) {
if (!h.empty()) h.pb (h[0]);
for (int j = 0; j < (int)h.sz - 1; ++j) {
a[h[j]][h[j + 1]] = 1;
a[h[j + 1]][h[j]] = 1;
}
}
}
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
for (int j = 0; j < n; ++j) {
if (a[i][j]) row[j] = 1;
}
answer.push_back(row);
}
build(answer);
return 1;
}
