#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int MAX_N = 1e3 + 5;
int n;
vector <int> graph[MAX_N];
bool visited[MAX_N];
vector <vector <int>> answer;
int cmp[MAX_N];
int parent[MAX_N];
vector <int> vertex[MAX_N];
int root(int u) {
if(u == parent[u]) {
return u;
}
return parent[u] = root(parent[u]);
}
void dfs(int u) {
visited[u] = true;
for(auto v : graph[u]) {
if(visited[v] == false) {
cmp[v] = cmp[u];
answer[u][v] = answer[v][u] = 1;
dfs(v);
}
}
}
int solve(vector <int> nodes, vector <vector <int>> p) {
bool two = false, three = false;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] == 1) {
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
for(int i = 0; i < n; i++) {
if(visited[i] == false) {
visited[i] = true;
cmp[i] = i;
dfs(i);
}
}
iota(parent, parent + n, 0);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] >= 2) {
if(p[i][j] == 2) {
two = true;
}
else {
three = true;
}
parent[root(cmp[j])] = root(cmp[i]);
}
}
}
if(two == true and three == true) {
return 0;
}
vector <int> cycle;
for(int i = 0; i < n; i++) {
if(cmp[i] == i) {
cycle.push_back(i);
}
}
if(two == true and cycle.size() <= 2) {
return 0;
}
if(three == true and cycle.size() <= 3) {
return 0;
}
if(two == true or three == true) {
int pr = cycle.back();
for(auto v : cycle) {
answer[v][pr] = answer[pr][v] = 1;
pr = v;
}
}
if(three == true) {
answer[cycle[0]][cycle[2]] = answer[cycle[2]][cycle[0]] = 1;
}
return 1;
}
int construct(vector <vector <int>> p) {
n = p.size();
fill(cmp, cmp + n, -1);
answer.resize(n, vector <int> (n, 0));
iota(parent, parent + n, 0);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] > 0) {
parent[root(j)] = root(i);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] == 0 and root(i) == root(j)) {
return 0;
}
}
}
vector <int> components;
for(int i = 0; i < n; i++) {
vertex[root(i)].push_back(i);
if(i == root(i)) {
components.push_back(i);
}
}
for(auto c : components) {
if(solve(vertex[c], p) == 0) {
return 0;
}
}
build(answer);
return 1;
}
