#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ufa;
int uf(int ind){
if(ufa[ind] == ind)return ind;
return ufa[ind] = uf(ufa[ind]);
}
int construct(vector<vector<int>> p) {
int n = p.size();
ufa.resize(n);
iota(ufa.begin(), ufa.end(), 0);
vector<vector<int>> tog(n);
vector<vector<int>> out(n, vector<int> (n,0));
vector<vector<int>> tre(n);
for(auto i : p)for(auto x : i)if(x==3)return 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(p[i][j]){
int a = uf(i);
int b = uf(j);
if(a == b)continue;
ufa[uf(i)] = ufa[uf(j)];
}
}
}
for(int i = 0; i < n; ++i){
tog[uf(i)].push_back(i);
}
iota(ufa.begin(), ufa.end(), 0);
for(int i = 0; i < n; ++i){
for(auto x : tog[i]){
for(auto y : tog[i]){
if(p[x][y] == 0)return 0;
if(p[x][y] == 1){
int a = uf(x);
int b = uf(y);
if(a == b)continue;
ufa[uf(x)] = ufa[uf(y)];
}
}
}
vector<int> cy;
for(auto x : tog[i]){
tre[uf(x)].push_back(x);
if(x == uf(x))cy.push_back(x);
}
if(cy.size() == 1)continue;
if(cy.size() == 2)return 0;
int cn = 1;
for(int j = 0; j < (int)cy.size(); ++j){
if(cn == (int)cy.size())cn = 0;
out[cy[j]][cy[cn]] = out[cy[cn]][cy[j]] = 1;
cn++;
}
}
for(int i = 0; i < n; ++i){
for(int j = 1; j < (int)tre[i].size(); ++j){
out[tre[i][0]][tre[i][j]] = out[tre[i][j]][tre[i][0]] = 1;
}
}
build(out);
return 1;
}
