#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<vector<int>> r;
int n;
vector<int> p(1005, -1);
int par(int x){
if(p[x]==-1)return x;
return p[x]=par(p[x]);
}
void merge(int a, int b){
int x=par(a), y=par(b);
if(x==y)return;
p[x]=y;
}
vector<vector<int>> comps;
vector<vector<int>> ans;
bool comp(vector<int> v){
//~ cout<<"COMPONENT : \n";
//~ for(auto it: v){
//~ cout<<it<<" ";
//~ }
//~ cout<<endl;
int mx=0;
for(auto node:v){
for(int j=0;j<n;j++){
mx=max(r[node][j], mx);
}
}
if(mx==0)return 1;
if(mx==1){
for(int i=0;i<(int)v.size()-1;i++){
ans[v[i]][v[i+1]]=1;
ans[v[i+1]][v[i]]=1;
}
return 1;
}
//~ cout<<"HERE"<<endl;
assert(mx==2);
for(auto node:v){
for(int j=0;j<n;j++){
if(r[node][j] == 1) merge(node, j);
}
}
for(auto node:v){
for(int j=0;j<n;j++){
if(r[node][j] == 2 and par(node)==par(j)) return 0;
}
}
//~ return 1;
vector<vector<int>> wings;
vector<int> label(1005, -1);
int t=0;
for(auto node : v){
if (label[par(node)] == -1){
wings.pb(vector<int>{node});
label[par(node)] = t++;
}
else wings[label[par(node)]].pb(node);
}
//~ cout<<"WINGS : \n";
//~ for(auto & wing : wings){
//~ for(auto & item : wing){
//~ cout<<item<<" ";
//~ }
//~ cout<<endl;
//~ }
//~ cout<<endl;
for(int i=0;i<(int)wings.size();i++){
for(int j=0;j<(int)wings[i].size()-1;j++){
ans[wings[i][j]][wings[i][j+1]]=1;
ans[wings[i][j+1]][wings[i][j]]=1;
}
if(i < (int)wings.size()){
ans[wings[i][0]][wings[(i+1)%(wings.size())][0]]=1;
ans[wings[(i+1)%(wings.size())][0]][wings[i][0]]=1;
}
}
return 1;
}
int construct(vector<vector<int>> coc) {
swap(r, coc);
n = r.size();
ans.resize(n);
for(int i=0;i<n;i++){
ans[i].resize(n);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//~ cout<<r[i][j]<<" ";
if(r[i][j])merge(i,j);
if(r[i][j]==3)return 0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!r[i][j] and par(i)==par(j)){
return 0;
}
}
}
vector<int> label(1005, -1);
int t=0;
for(int i=0;i<n;i++){
if (label[par(i)] == -1){
comps.pb({i});
label[par(i)] = t++;
}
else comps[label[par(i)]].pb(i);
}
for(int i=0;i<n;i++)p[i]=-1; // reset;
for(int i=0;i<(int)comps.size();i++){
if(!comps[i].empty()){
//~ cout<<"COMP "<<i<<endl;
int res=comp(comps[i]);
if(!res) return 0;
}
}
//~ for(int i=0;i<n;i++)ans[i][i]=1;
//~ for(auto & row : ans){
//~ for(auto & item : row){
//~ cout<<item<<" ";
//~ }
//~ cout<<endl;
//~ }
build(ans);
return 1;
}
