#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define pll array<ll, 2>
#define pb push_back
using namespace std;
ll n;
vector<vector<int>>g;
struct DSU{
vector<ll>e;
DSU(ll n){e.assign(n + 1, -1);}
ll find(ll x){
if(e[x] < 0) return x;
return e[x] = find(e[x]);
}
bool unite(ll a, ll b){
a = find(a), b = find(b);
if(a == b) return 0;
if(e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return 1;
}
};
int construct(vector<vector<int>> p) {
ll n = p.size(); DSU dsu(n);
g.assign(n, vector<int>(n, 0));
for(ll i = 0; i < n; i++){
for(ll j = 0; j < n; j++){
if(p[i][j]) dsu.unite(i, j);
if(p[i][j] == 3) return 0;
}
}
for(ll i = 0; i < n; i++){
for(ll j = 0; j < n; j++){
ll rt1 = dsu.find(i);
ll rt2 = dsu.find(j);
if(!p[i][j] and rt1 == rt2) return 0;
}
}
map<ll, vector<ll>>comp;
for(ll i = 0; i < n; i++){
ll rt = dsu.find(i);
comp[rt].pb(i);
}
for(auto &[rt , vv] : comp){
if(vv.size() == 1) continue;
set<ll>cycle; pll cnt = {0, 0};
for(ll i = 1; i < vv.size(); i++){
cnt[p[vv[0]][vv[i]] - 1]++;
}
if(cnt[0] and !cnt[1]){
for(ll i = 1; i < vv.size(); i++){
g[vv[0]][vv[i]] =
g[vv[i]][vv[0]] = 1;
}
continue;
}
map<ll, set<ll>>ones;
vector<bool>ch(n, 0);
for(ll &i : vv){
if(ch[i]) continue;
ll c = 0;
for(ll &j : vv){
if(i == j) continue ;
c += (p[i][j] > 1);
}
if(c == vv.size() - 1) cycle.insert(i);
else{
for(ll &j : vv){
if(i == j) continue;
if(p[i][j] == 1){
ones[i].insert(j);
ch[j] = 1;
}
}
}
ch[i] = 1;
}
vector<ll>path;
for(auto &[x, adj] : ones){
for(ll i : adj){
g[i][x] = 1;
g[x][i] = 1;
}
path.pb(x);
}
ll prev = *cycle.begin();
for(ll i : cycle){
if(i == prev) continue;
g[i][prev] = 1;
g[prev][i] = 1;
prev = i;
}
for(ll i = 0; i < path.size(); i++){
g[prev][path[i]] = 1;
g[path[i]][prev] = 1;
prev = path[i];
}
g[*cycle.begin()][prev] = 1;
g[prev][*cycle.begin()] = 1;
}
build(g);
return 1;
}
