#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>>p){
int n = p.size();
bool is_sub1 = true, is_sub2 = true, is_sub3 = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] != 1){
is_sub1 = false;
}
if(p[i][j] > 1){
is_sub2 = false;
}
if(p[i][j] != 0 && p[i][j] != 2){
is_sub3 = false;
}
}
}
if(is_sub1){
p = vector<vector<int>>(n, vector<int>(n, 0));
for(int i = 1; i < n; i++){
p[i][i - 1] = p[i - 1][i] = 1;
}
build(p);
return 1;
}
if(is_sub2){
vector<int>par(n);
iota(par.begin(), par.end(), 0);
function<int(int)>find_set;
find_set = [&] (int n){
return n == par[n] ? n : par[n] = find_set(par[n]);
};
function<void(int, int)>merge = [&] (int a, int b){
par[find_set(a)] = find_set(b);
};
vector<bool>vis(n, false);
vector<vector<int>>edge(n);
for(int i = 0; i < n; i++){
if(vis[i]){
for(int j = 0; j < n; j++){
if(i != j && int(find_set(i) == find_set(j)) != p[i][j]){
return 0;
}
}
continue;
}
for(int j = 0; j < n; j++){
if(i != j && p[i][j] == 0 && find_set(i) == find_set(j)){
return 0;
}
if(p[i][j] == 1){
merge(i, j);
vis[j] = true;
}
}
}
for(int i = 0; i < n; i++){
edge[find_set(i)].emplace_back(i);
}
p = vector<vector<int>>(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
for(int j = 1; j < edge[i].size(); j++){
p[edge[i][j]][edge[i][j - 1]] = p[edge[i][j - 1]][edge[i][j]] = 1;
}
}
build(p);
return 1;
}
if(is_sub3){
vector<int>par(n);
iota(par.begin(), par.end(), 0);
function<int(int)>find_set;
find_set = [&] (int n){
return n == par[n] ? n : par[n] = find_set(par[n]);
};
function<void(int, int)>merge = [&] (int a, int b){
par[find_set(a)] = find_set(b);
};
vector<bool>vis(n, false);
vector<vector<int>>edge(n);
for(int i = 0; i < n; i++){
if(vis[i]){
for(int j = 0; j < n; j++){
if(i != j && (find_set(i) == find_set(j)) != (p[i][j] == 2)){
return 0;
}
}
continue;
}
for(int j = 0; j < n; j++){
if(i != j && p[i][j] == 0 && find_set(i) == find_set(j)){
return 0;
}
if(p[i][j] == 2){
merge(i, j);
vis[j] = true;
}
}
}
for(int i = 0; i < n; i++){
edge[find_set(i)].emplace_back(i);
}
p = vector<vector<int>>(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
if(edge[i].size() == 2){
return 0;
}
if(edge[i].size() > 2){
edge[i].emplace_back(edge[i][0]);
for(int j = 1; j < edge[i].size(); j++){
p[edge[i][j]][edge[i][j - 1]] = p[edge[i][j - 1]][edge[i][j]] = 1;
}
}
}
build(p);
return 1;
}
vector<int>par(n);
iota(par.begin(), par.end(), 0);
function<int(int)>find_set;
find_set = [&] (int n){
return n == par[n] ? n : par[n] = find_set(par[n]);
};
function<void(int, int)>merge = [&] (int a, int b){
par[find_set(a)] = find_set(b);
};
vector<bool>vis(n, false), all_2(n, true);
vector<vector<int>>edge(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 1){
all_2[i] = false;
break;
}
}
}
for(int i = 0; i < n; i++){
if(vis[i]){
for(int j = 0; j < n; j++){
if(i != j && (find_set(i) == find_set(j)) != (p[i][j] > 0)){
return 0;
}
}
}
if(!all_2[i]){
for(int j = 0; j < n; j++){
if(i != j && p[i][j] == 0 && find_set(i) == find_set(j)){
return 0;
}
if(p[i][j] > 0){
merge(i, j);
vis[j] = true;
}
}
}
}
for(int i = 0; i < n; i++){
if(all_2[i]){
if(!vis[i]){
for(int j = 0; j < n; j++){
if(p[i][j] > 0){
if(vis[j]){
return 0;
}
vis[j] = true;
merge(i, j);
}
}
}
else{
for(int j = 0; j < n; j++){
if(i != j && (find_set(i) == find_set(j)) != (p[i][j] > 0)){
return 0;
}
}
}
}
edge[find_set(i)].emplace_back(i);
}
vector<vector<int>>ans(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
vector<vector<int>>part(2);
for(int& j : edge[i]){
part[all_2[j]].emplace_back(j);
}
if(part[0].empty()){
if(part[1].size() == 2){
return 0;
}
if(part[1].size() > 2){
part[1].emplace_back(part[1][0]);
for(int j = 1; j < part[1].size(); j++){
ans[part[1][j]][part[1][j - 1]] = ans[part[1][j - 1]][part[1][j]] = 1;
}
}
}
else{
for(int& index : part[0]){
if(p[index] != p[part[0][0]]){
return 0;
}
}
for(int j = 1; j < part[0].size(); j++){
ans[part[0][j]][part[0][j - 1]] = ans[part[0][j - 1]][part[0][j]] = 1;
}
if(part[1].size() == 1){
return 0;
}
part[1].emplace_back(part[0].back());
for(int j = 1; j < part[1].size(); j++){
ans[part[1][j]][part[1][j - 1]] = ans[part[1][j - 1]][part[1][j]] = 1;
}
}
}
build(ans);
return 1;
}
