#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a.begin(), a.end())
#define sz(a) (int)a.size()
int n;
int construct(std::vector<std::vector<int>> p) {
n=sz(p);
vector<vector<int>> groups;
vector<int> id(n);
for (int i = 0; i < n; i++)
{
int g=-1;
for (int j = 0; j < i; j++)
{
if(p[i][j]>=1) {
if(g>-1&&id[j]!=g) return 0;
g=id[j];
}
}
if(g==-1) { groups.push_back({i}); id[i]=sz(groups)-1; }
else {
id[i]=g;
groups[g].push_back(i);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if((bool)p[i][j]!=(bool)(id[i]==id[j])) return 0;
}
}
vector<vector<int>> bridge(n,vector<int>(n));
/*for (int i = 0; i < sz(groups); i++)
{
for (int j = 1; j < sz(groups[i]); j++)
{
bridge[groups[i][j-1]][groups[i][j]]=bridge[groups[i][j]][groups[i][j-1]]=1;
}
}*/
for (int i = 0; i < sz(groups); i++)
{
if(sz(groups[i])==1) continue;
set<int> al;
for (int j = 0; j < sz(groups[i]); j++)
{
bool b=true;
for (int k = 0; k < sz(groups[i]); k++)
{
if(j==k) continue;
if(p[groups[i][j]][groups[i][k]]<=1) b=false;
}
if(b) al.insert(groups[i][j]);
}
for (int j = 0; j < sz(groups[i]); j++)
{
if(al.find(groups[i][j])!=al.end()) continue;
for (int k = 0; k < sz(groups[i]); k++)
{
if(j==k) continue;
//if(p[groups[i][j]][groups[i][k]]==2&&al.find(groups[i][k])==al.end()) return 0;
}
}
int prev=-1;
for (int j = 0; j < sz(groups[i]); j++)
{
if(al.find(groups[i][j])!=al.end()) continue;
if(prev!=-1) bridge[prev][groups[i][j]]=bridge[groups[i][j]][prev]=1;
prev=groups[i][j];
}
if(sz(al)==1&&sz(groups[i])>=2) return 0;
if(sz(al)==2&&sz(groups[i])>=2) return 0;
if(sz(al)>0){
if(prev==-1) bridge[*al.begin()][*al.rbegin()]=bridge[*al.rbegin()][*al.begin()]=1;
else bridge[prev][*(al.rbegin())]=bridge[*(al.rbegin())][prev]=1;
}
for (auto u : al)
{
if(prev!=-1) bridge[prev][u]=bridge[u][prev]=1;
prev=u;
}
}
build(bridge);
return 1;
}
