#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<pair<int,int>>> adj(n);
vector<vector<int>> answer(n,vector<int> (n,0));
vector<int> cnt1(n,1);
L(i,0,n-1){
if(p[i][i]!=1)return 0;
L(j,0,n-1){
if(p[i][j]==3)return 0;
if(i!=j && p[i][j]!=0){
adj[i].push_back({j,p[i][j]});
if(p[i][j]==1)cnt1[i]++;
}
}
}
vector<vector<int>> grupos;
int gat=0;
vector<int> grupo(n,-1);
auto dfsg=[&](auto&& self, int node,int g)->void{
grupos.back().push_back(node);
grupo[node]=g;
for(auto [a,t]:adj[node]){
if(grupo[a]==-1){
self(self,a,g);
}
}
return;
};
L(i,0,n-1){
if(grupo[i]==-1){
grupos.push_back({});
dfsg(dfsg,i,gat);
gat++;
}
}
for(auto& g:grupos){//grupos sao conexos
for(auto&a :g){
for(auto&b:g){
if(p[a][b]==0)return 0;
}
}
}
vector<int> goat(n,-1);
vector<vector<int>> sub(n);
for(auto&g: grupos){
int cnt=0;
vector<int> goats;
for(auto a:g){
if(goat[a]==-1){
goats.push_back(a);
cnt++;
goat[a]=a;
sub[a].push_back(a);
for(auto [b,tipo]:adj[a]){
if(tipo!=1)continue;
answer[a][b]=answer[b][a]=1;
goat[b]=a;
sub[a].push_back(b);
}
}
}
for(auto a:g){
if(sub[a].empty())continue;
for(auto b:sub[a]){
for(auto c:sub[a]){
if(p[b][c]!=1)return 0;
}
if(cnt1[b]!=sz(sub[a]))return 0;//garanto que o resto estrito eh com 2
}
}
if(cnt==2)return 0;
if(cnt==1)continue;
L(i,0,sz(goats)-1){
int xx=goats[i%sz(goats)];
int yy=goats[(i+1)%sz(goats)];
answer[xx][yy]=answer[yy][xx]=1;
}
}
build(answer);
return 1;
}
