#include <bits/stdc++.h>
#include "supertrees.h"
#define DIM 1010
using namespace std;
int t[DIM],t2[DIM],a[DIM][DIM],f[DIM],last[DIM];
vector <int> v[DIM],w;
/*void build (vector <vector <int> > a){
int n = a.size();
for (int i=0;i<n;i++,cout<<"\n")
for (int j=0;j<n;j++)
cout<<a[i][j]<<" ";
}*/
int get_rad (int t[], int x){
while (t[x] > 0)
x = t[x];
return x;
}
void uneste (int t[], int x, int y){
int radx = get_rad (t,x), rady = get_rad (t,y);
if (radx == rady)
return;
if (t[radx] > t[rady])
swap (radx,rady);
t[radx] += t[rady];
t[rady] = radx;
}
int construct (vector <vector<int> > p){
int n = p.size();
memset (t,-1,sizeof t);
memset (f,0,sizeof f);
for (int i=1;i<=n;i++)
v[i].clear();
int ok = 0;
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if (p[i][j]){
uneste (t,i+1,j+1);
if (p[i][j] == 3)
ok = 1;
}
if (ok)
return 0;
int nr_comp = 0;
for (int i=1;i<=n;i++){
int rad = get_rad (t,i);
if (!f[rad])
f[rad] = ++nr_comp;
/// mai verific daca e conectat cu toate nodurile din componenta
for (auto it : v[f[rad]]){
if (p[it-1][i-1] == 0)
return 0;
}
v[f[rad]].push_back(i);
}
for (int i=1;i<=nr_comp;i++){
/// fac iar paduri cu nodurile din multimea asta
memset (t2,-1,sizeof t2);
memset (last,0,sizeof last);
for (auto it : v[i]){
for (auto it2 : v[i]){
if (it != it2 && p[it-1][it2-1] == 1)
uneste (t2,it,it2);
}}
w.clear();
for (auto it : v[i]){
int rad = get_rad (t2,it);
if (t2[rad] == -1){
w.push_back(it);
continue;
}
if (!last[rad]){
last[rad] = it;
w.push_back(it);
} else {
a[last[rad]][it] = a[it][last[rad]] = 1;
last[rad] = it;
}
}
if (w.size() == 2)
return 0;
for (int j=0;j<w.size()-1;j++)
a[w[j]][w[j+1]] = a[w[j+1]][w[j]] = 1;
if (w.size() > 1)
a[w[0]][ w[w.size()-1] ] = a[ w[w.size()-1] ][w[0]] = 1;
}
vector <vector<int> > ans;
for (int i=1;i<=n;i++){
vector <int> lin;
for (int j=1;j<=n;j++)
lin.push_back(a[i][j]);
ans.push_back (lin);
}
build (ans);
return 1;
}
