#include "supertrees.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<int> parent;
vector<int> sz;
int getParent(int a){
if(parent[a]==a) return a;
return parent[a]=getParent(parent[a]);
}
void unite(int a, int b){
a=getParent(a); b=getParent(b);
if(a==b) return;
if(sz[a]>sz[b]) swap(a,b);
parent[b]=a;
sz[a]+=sz[b];
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<signed>> answer(n,vector<int>(n));
vector<pair<int,int>> ed;
parent.resize(n);
sz.resize(n,1);
for (int i = 0; i < n; i++) parent[i]=i;
vector<vector<int>> con(n,vector<int>(n,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{
if(p[i][j]==1){
if(getParent(i)==getParent(j)) continue;
ed.push_back({i,j});
unite(i,j);
}
}
}
for (int i = 0; i < n; i++) con[i][i]=1;
vector<bool> used(n);
for (int i = 0; i < n; i++)
{
if(used[getParent(i)]) continue;
used[getParent(i)]=true;
set<int> st;
for (int j = 0; j < n; j++)
{
if(p[i][j]==2){
st.insert(getParent(j));
}
}
if(sz(st)==0) continue;
if(sz(st)==1) return 0;
int lst=getParent(i);
for (auto u : st)
{
ed.push_back({u,lst});
lst=u;
used[u]=true;
}
ed.push_back({getParent(i),lst});
st.insert(getParent(i));
for (auto u : st){
for (auto v : st){
if(u==v) continue;
con[u][v]=con[v][u]=2;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(p[i][j]!=con[getParent(i)][getParent(j)]) return 0;
}
}
for (auto u : ed)
{
answer[u.first][u.second]=answer[u.second][u.first]=1;
}
build(answer);
return 1;
}
