#include "supertrees.h"
#include <vector>
using namespace std;
int uf[1006];
int _find(int x) {
if (uf[x] == -1) return x;
return uf[x] = _find(uf[x]);
}
void _merge(int x, int y) {
x = _find(x), y = _find(y);
if (x != y) uf[x] = y;
}
vector<int> v[1006], u[1006];
vector<vector<int>> adj;
int construct(vector<vector<int>> p) {
int n = p.size();
adj.resize(n);
for (int i = 0; i < n; i++) adj[i].resize(n, 0);
for (int i = 0; i < n; i++) uf[i] = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (p[i][j]) _merge(i, j);
for (int i = 0; i < n; i++) v[_find(i)].push_back(i);
for (int t = 0; t < n; t++) for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (p[v[t][i]][v[t][j]] == 0 || p[v[t][i]][v[t][j]] == 3) return 0;
for (int t = 0; t < n; t++) if (!v[t].empty()) {
for (int i = 0; i < n; i++) uf[i] = -1, u[i].clear();
for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (p[v[t][i]][v[t][j]] == 1) _merge(v[t][i], v[t][j]);
for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (_find(v[t][i]) == _find(v[t][j]) && p[v[t][i]][v[t][j]] == 2) return 0;
for (int i = 0; i < (int)v[t].size(); i++) u[_find(v[t][i])].push_back(v[t][i]);
vector<int> cycle;
for (int i = 0; i < n; i++) if (!u[i].empty()) {
cycle.push_back(u[i][0]);
for (int j = 1; j < (int)u[i].size(); j++) adj[u[i][j - 1]][u[i][j]] = adj[u[i][j]][u[i][j - 1]] = 1;
}
for (int i = 1; i < (int)cycle.size(); i++) adj[cycle[i - 1]][cycle[i]] = adj[cycle[i]][cycle[i - 1]] = 1;
if ((int)cycle.size() > 2) adj[cycle.back()][cycle[0]] = adj[cycle[0]][cycle.back()] = 1;
else if ((int)cycle.size() == 2) return 0;
}
build(adj);
return 1;
}
