#include "supertrees.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
#define f0(i, n) for (int i = 0; i < n; i++)
#define f1(i, n) for (int i = 1; i <= n; i++)
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
f0(i, n) {
f0(j, n) {
if(p[i][j] == 3) {
return 0;
}
if(p[i][j] != p[j][i]) {
return 0;
}
}
if(p[i][i] != 1) {
return 0;
}
}
// okay
vector<vector<pair<int, int>>> graph(n);
f0(i, n) {
f0(j, n) {
if(p[i][j] == 0) continue;
if(i == j) continue;
graph[i].push_back({p[i][j], j});
}
}
f0(i, n) {
sort(graph[i].begin(), graph[i].end());
}
// okay
std::vector<std::vector<int>> b;
for (int i = 0; i < n; i++) {
std::vector<int> row(n, 0);
row.resize(n);
b.push_back(row);
}
// okay
vector<vector<int>> groups;
bool used[n] = {0};
f0(i, n) {
if(used[i]) continue;
vector<int> group;
group.push_back(i);
used[i] = true;
queue<int> q;
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(used[v.second]) continue;
used[v.second] = true;
group.push_back(v.second);
q.push(v.second);
}
}
for(int u: group) {
for(int v: group) {
if(p[u][v] == 0) {
return 0;
}
}
}
groups.push_back(group);
}
// okay
for(auto group : groups) {
vector<vector<int>> g;
for(int i : group) {
if(!used[i]) continue;
vector<int> gg;
gg.push_back(i);
used[i] = false;
for(auto pp: graph[i]) {
if(pp.first == 2) break;
gg.push_back(pp.second);
used[pp.second] = false;
}
g.push_back(gg);
}
// okay
// for(auto gg: g) {
// for(int i: gg) {
// cout << i << " ";
// }
// cout << endl;
// }
int nn = g.size();
if(nn == 2) return 0;
f0(i, nn) {
if(nn != 1) {
b[g[i][0]][g[(i+1)%nn][0]] = 1;
b[g[(i+1)%nn][0]][g[i][0]] = 1;
}
int nnn = g[i].size();
f1(j, nnn-1) {
b[g[i][j]][g[i][j-1]] = 1;
b[g[i][j-1]][g[i][j]] = 1;
}
}
// okay
f0(i, nn) {
for(int j = i+1; j < nn; j++) {
for(int u: g[i]) {
for(int v: g[j]) {
if(p[u][v] != 2) {
return 0;
}
if(p[v][u] != 2) {
return 0;
}
}
}
}
for(int u: g[i]) {
for(int v: g[i]) {
if(p[u][v] != 1) {
return 0;
}
}
}
}
}
build(b);
return 1;
}
