#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> nodes[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 construct(vector <vector <int>> p) {
n = p.size();
answer.resize(n, vector <int> (n, 0));
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) {
parent[root(cmp[j])] = root(cmp[i]);
}
}
}
for(int i = 0; i < n; i++) {
if(cmp[i] == i) {
nodes[root(i)].push_back(i);
}
}
for(int i = 0; i < n; i++) {
if(root(i) == i and i == cmp[i] and nodes[i].size() > 1) {
if(nodes[i].size() == 2) {
return 0;
}
int p = nodes[i].back();
for(auto v : nodes[i]) {
answer[v][p] = answer[p][v] = 1;
p = v;
}
}
}
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;
}
}
}
build(answer);
return 1;
}
