#include "supertrees.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int>parent;
vector<int>sz;
vector<vector<int>>comp;
void build(int n){
parent.resize(n);
sz.resize(n);
comp.resize(n);
for (int i = 0;i<n;++i){
parent[i] = i;
sz[i] = 1;
comp[i].push_back(i);
}
}
int findsets(int v){
if (v == parent[v])return v;
parent[v] = findsets(parent[v]);
return parent[v];
}
bool unionset(int a,int b){
int u = findsets(a);
int v = findsets(b);
if (u == v)return false;
if (sz[u] < sz[v])swap(u,v);
parent[v] = u;
sz[u]+=sz[v];
sz[v] = 0;
while(!comp[v].empty()){
comp[u].push_back(comp[v].back());
comp[v].pop_back();
}
return true;
};
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer(n,vector<int>(n,0));
for (int i = 0;i<n;++i){
for (int j = 0;j<n;++j){
if (p[i][j] == 3)return 0;
}
}
DSU st;
st.build(n);
for (int i = 0;i<n;++i){
for (int j = i + 1;j<n;++j){
int u = st.findsets(i);
int v = st.findsets(j);
if (p[i][j]==1 && st.unionset(i,j)){
answer[u][v] = true;
answer[v][u] = true;
}
}
}
vector<vector<bool>>pre(n,vector<bool>(n,false));
vector<bool>wt(n,false);
for (int i = 0;i<n;++i){
for (int j = i + 1;j<n;++j){
if (st.findsets(i) == st.findsets(j)){
p[i][j]--;
p[j][i]--;
pre[i][j] = true;
pre[j][i] = true;
wt[i] = true;
wt[j] = true;
}
}
}
for (int i = 0;i<n;++i){
if (i == st.findsets(i))wt[i] = false;
}
for (int i = 0;i<n;++i){
bool got = true;
if (i == st.findsets(i) && got){
vector<int>par(n,-1);
got =false;
function<void(int)> dfs = [&](int u){
if (u == i && par[u]!=-1 && !got){
int x = par[u];
answer[u][x] = true;
answer[x][u] = true;
got = true;
while(x != u){
for (auto q:st.comp[i]){
p[q][x]--;
p[x][q]--;
}
st.unionset(i,x);
answer[x][par[x]] = true;
answer[par[x]][x] = true;
x = par[x];
}
for (auto q:st.comp[i]){
for (auto qq:st.comp[i]){
if (!pre[q][qq] && q!=qq)
p[q][qq]--;
}
}
return;
}
for (int j = 0;j<n;++j){
if (j == u)continue;
if (p[u][j]!=2)continue;
if (wt[j])continue;
if (j == par[u])continue;
if (par[j]==-1){
par[j] = u;
dfs(j);
par[j] =-1;
}
}
};
dfs(i);
}
}
for (int i = 0;i<n;++i){
for (int j = 0;j < n;++j){
if (i == j)continue;
if (p[i][j] != 0){
//cout<<i<<" "<<j<<" "<<p[i][j]<<'\n';
return 0;
}
}
}
build(answer);
return 1;
}
