#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define all(c) ((c).begin()), ((c).end())
struct dsu{
vector<vector<int>> components;
int n;
vector<int> par;
dsu(int n) : n(n), par(n){
iota(all(par), 0);
components.resize(n);
for(int i = 0; i < n; i++) components[i] = {i};
}
int root(int x){
return (x == par[x]) ? x : (par[x] = root(par[x]));
}
void merge(int x, int y){
x = root(x); y = root(y);
if(x == y) return;
copy(all(components[x]), back_inserter(components[y]));
components[x].clear();
par[x] = y;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n, vector<int>(n, 0));
function<void(int, int)> add_edge = [&](int x, int y){
adj[x][y] = adj[y][x] = 1;
};
dsu D(n);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(p[i][j] > 0) D.merge(i, j);
}
}
for(int i = 0; i < n; i++) if(D.par[i] == i){
vector<int> v = D.components[i];
for(int x : v) for(int y : v) if(p[x][y] == 0 || p[x][y] == 3) return 0;
dsu D2(n);
for(int x : v) for(int y : v) if(x != y && p[x][y] == 1) D2.merge(x, y);
vector<int> cycle;
for(int x : v) if(D2.par[x] == x){
cycle.push_back(x);
vector<int> U = D2.components[x];
int lst = -1;
for(int a : U){
for(int b : U) if(p[a][b] != 1) return 0;
if(lst != -1) add_edge(a, lst);
lst = a;
}
}
int m = cycle.size();
if(m == 2) return 0;
if(m > 1)
for(int k = 0; k < m; k++) add_edge(cycle[k], cycle[(k + 1) % m]);
}
build(adj);
return 1;
}
