#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
const int MX = 1042;
bool vis[MX];
bool vis2[MX];
int cycleId[MX];
int rep[MX];
int cycleRep[MX];
int compId[MX];
int nxtComp = 0;
int nxtCycle = 0;
vector<int> adj[MX];
vector<int> adj2[MX];
vector<int> comp[MX];
vector<int> comp2[MX];
void dfs(int node, int r, int c) {
vis[node] = true;
rep[node] = r;
compId[node] = c;
comp[c].push_back(node);
for (auto& x: adj[node])
if (!vis[x])
dfs(x, r, c);
}
void dfs2(int node, int r, int c) {
vis2[node] = true;
cycleRep[node] = r;
cycleId[node] = c;
comp2[c].push_back(node);
for (auto& x: adj2[node])
if (!vis2[x])
dfs2(x, r, c);
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1 && i != j) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
//cout << "dfs root " << i << '\n';
dfs(i, i, nxtComp++);
}
}
for (int i = 0; i < n; i++) {
if (rep[i] == i) {
// add cycles
for (int j = 0; j < n; j++) {
if (rep[j] != i) {
for (auto& x: comp[compId[i]]) {
if (p[j][x] == 2) {
//cout << "fuke " << i << ' ' << rep[j] << '\n';
adj2[i].push_back(rep[j]);
adj2[rep[j]].push_back(i);
}
}
}
}
// add chain
for (auto& a: comp[compId[i]]) {
for (auto& b: comp[compId[i]]) {
if (a != b) {
answer[a][b] = answer[b][a] = 1;
}
}
}
}
}
for (int i = 0; i < n; i++) {
if (!vis2[i]) {
dfs2(i, i, nxtCycle++);
}
}
// add cycle edges
for (int i = 0; i < n; i++) {
if (rep[i] == i) {
//cout << "comp of " << i << '\n';
for (auto& x: comp[compId[i]]) {
//cout << x << '\n';
cycleId[x] = cycleId[i];
}
}
if (cycleRep[i] == i) {
int sz = (int)comp2[cycleId[i]].size();
if (sz == 2)
return 0;
for (int j = 0; sz > 1 && j < sz; j++) {
answer[comp2[cycleId[i]][j]][comp2[cycleId[i]][(j + 1) % sz]] = 1;
answer[comp2[cycleId[i]][(j + 1) % sz]][comp2[cycleId[i]][j]] = 1;
//cout << "cycle edge from " << comp2[cycleId[i]][j] << ' ' << comp2[cycleId[i]][j + 1] << '\n';
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
if (p[i][j] == 0 && cycleId[i] == cycleId[j])
return 0;
if (p[i][j] == 1 && rep[i] != rep[j])
return 0;
if (p[i][j] == 2 && !((cycleId[i] == cycleId[j]) && (rep[i] != rep[j])))
return 0;
}
}
}
build(answer);
return 1;
}
