#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
bool solve(ll n, vector<ll> v, vector<vector<ll>> &p, vector<vector<ll>> &ans){
vector<bool> vis(n);
vector<vector<ll>> c(n);
for(ll i: v) if(!vis[i]){
for(ll j = 0; j < n; j++) if(p[i][j] == 1) c[i].push_back(j), vis[j] = 1;
}
vector<ll> cyc;
for(ll i = 0; i < n; i++) if(c[i].size()) {
if(cyc.size()) ans[cyc.back()][c[i][0]] = ans[c[i][0]][cyc.back()] = 1;
cyc.push_back(c[i][0]);
for(ll j = 1; j < c[i].size(); j++) ans[c[i][j-1]][c[i][j]] = ans[c[i][j]][c[i][j-1]] = 1;
}
if(cyc.size() > 1) ans[cyc[0]][cyc.back()] = ans[cyc.back()][cyc[0]] = 1;
return 1;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<bool> vis(n);
vector<vector<ll>> ans(n, vector<ll>(n));
for(ll i = 0; i < n; i++) if(!vis[n]){
vector<ll> comp;
for(ll j = 0; j < n; j++) if(p[i][j]) comp.push_back(j), vis[j] = 1;
solve(n, comp, p, ans);
}
build(ans);
return 1;
}
