#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef vector<int> IVec;
void addEdge(int u, int v, vector<IVec>& G) { G[u][v] = G[v][u] = 1; }
int construct(vector<IVec> p) {
int n = p.size();
for (int i = 0; i < n; i++) // if p(i,j) == 3, there must be another p(i`,j`) ≥4 ??
if (find(p[i].begin(), p[i].end(), 3) != p[i].end()) return 0;
vector<vector<int>> G(n, IVec(n));
vector<bool> Vis(n);
IVec CC(n), TreeID(n);
for (int u = 0; u < n; u++) {
if (Vis[u]) continue;
queue<int> cycleQ; cycleQ.push(u);
IVec cycle; // cycle containing u
while (!cycleQ.empty()) {
int root = cycleQ.front(); cycleQ.pop();
if (Vis[root]) continue;
IVec tree; // tree contains root
queue<int> treeQ; treeQ.push(root);
cycle.push_back(root);
while (!treeQ.empty()) { // bfs to mark all points in tree root
int v = treeQ.front(); treeQ.pop();
if (Vis[v]) continue;
tree.push_back(v), TreeID[v] = root;
Vis[v] = true, CC[v] = u;
for (int i = 0; i < n; i++) {
if (p[v][i] == 2) cycleQ.push(i); // v and i should on same circle
else if (p[v][i] == 1) treeQ.push(i); // v and i on same tree
}
}
for (size_t i = 0; i + 1 < tree.size(); i++)
addEdge(tree[i], tree[i + 1], G);
}
int csz = cycle.size();
if (csz == 2) return 0;
if (csz > 2)
for (int i = 0; i < csz; i++) addEdge(cycle[i], cycle[(i + 1) % csz], G);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int pc = p[i][j];
if (TreeID[i] == TreeID[j]) { if (pc != 1) return 0; }
else if (CC[i] == CC[j]) { if (pc != 2) return 0; }
else { if (pc) return 0; }
}
}
build(G);
return 1;
}
