#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,vector<vector<int>>&p,vector<vector<int>>&answer,bool ok){
int u = findsets(a);
int v = findsets(b);
if (sz[u] < sz[v])swap(u,v);
set<pair<int,int>>brr;
if (ok && u == v)return false;
for (auto x:comp[v]){
for (auto y:comp[u]){
if (x == y)continue;
if (brr.find({x,y})!=brr.end())continue;
if (answer[x][y])continue;
if (!p[x][y])return false;
p[x][y]--;
p[y][x]--;
brr.insert({x,y});
brr.insert({y,x});
}
}
bool got = false;
for (auto x:comp[v]){
for (auto y:comp[u]){
if (!answer[x][y] && x != y){
answer[x][y] = true;
answer[y][x] = true;
got = true;
break;
}
}
if (got)break;
}
if (ok){
parent[v] = u;
sz[u]+=sz[v];
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));
DSU st;
st.build(n);
for (int i = 0;i<n;++i){
for (int j = i + 1;j<n;++j){
if (p[i][j]){
st.unionset(i,j,p,answer,1);
}
}
}
for (int i = 0;i<n;++i){
for (int j = i + 1;j<n;++j){
if (p[i][j]){
if (!st.unionset(i,j,p,answer,0)){
return 0;
}
}
}
}
for (int i = 0;i<n;++i){
for (int j = 0;j < n;++j){
if (i == j)continue;
if (p[i][j])return 0;
}
}
build(answer);
return 1;
}
