#include "supertrees.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int inf = 1e9 + 7;
/*
void build(vector<vector<int>> b) {
int n = b.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (b[i][j] == 1) {
cout << i << ' ' << j << endl;
}
}
}
}*/
struct dsu {
vector<int> par;
vector<int> sz;
void init(int n) {
par.assign(n, 0);
sz.assign(n, 1);
for (int i = 0; i < n; i++) {
par[i] = i;
}
}
int get_par(int v) {
if (par[v] == v) {
return v;
}
int ans = get_par(par[v]);
par[v] = ans;
return ans;
}
void unitik(int v, int u) {
v = get_par(v);
u = get_par(u);
if (sz[v] < sz[u]) {
swap(v, u);
}
sz[v] += sz[u];
par[u] = v;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
dsu dsu;
dsu.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0 && dsu.get_par(i) != dsu.get_par(j)) {
dsu.unitik(i, j);
}
}
}
bool ok = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 0 && dsu.get_par(i) == dsu.get_par(j)) {
ok = 0;
}
}
}
if (!ok) {
return 0;
}
vector<vector<int>> b(n, vector<int>(n));
vector<vector<int>> gr(n);
for (int i = 0; i < n; i++) {
gr[dsu.get_par(i)].push_back(i);
}
for (int j = 0; j < n; j++) {
if (gr[j].size() < 2)
continue;
if (gr[j].size() == 2)
return 0;
for (int i = 0; i < gr[j].size(); i++) {
b[gr[j][i]][gr[j][(i + 1) % gr.size()]] = 1;
b[gr[j][(i + 1) % gr.size()]][gr[j][i]] = 1;
}
}
build(b);
return 1;
}
/*
int main() {
int n;
cin >> n;
vector<vector<int>> w(n, vector<int> (n, 1));
int va = construct(w);
}*/
