#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> parent, Size;
int findUpar(int node){
if(node == parent[node]) return node;
return parent[node] = findUpar(parent[node]);
}
void U(int u, int v){
int pu = findUpar(u), pv = findUpar(v);
if(pu == pv) return;
if(Size[pu] > Size[pv]){
parent[pv] = pu;
Size[pu] += Size[pv];
}else{
parent[pu] = pv;
Size[pv] += Size[pu];
}
}
int construct(vector<vector<int>>p){
int n = p.size(); parent.resize(n); Size.resize(n);
for(int i = 0; i<n; i++) parent[i] = i, Size[i] = 1;
vector<vector<int>>adj(n, vector<int>(n, 0));
vector<pair<int,int>>zero, two;
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(p[i][j] == 0){
zero.push_back({i, j});
}else if(p[i][j] == 1){
for(int k = 0; k<n; k++){
if(p[j][k] == 1){
if(!(p[i][k] == 1)){
return 0;
}
}
}
U(i, j);
}else if(p[i][j] == 2){
for(int k = 0; k<n; k++){
if(p[j][k] > 0){
if(!(p[i][k] > 0)){
return 0;
}
}
}
two.push_back({i, j});
}else if(p[i][j] == 3){
return 0;
}
}
}
//mark 1
for(int i = 0; i<n; i++){
int pi = findUpar(i);
if(i != pi){
adj[i][pi] = 1; adj[pi][i] = 1;
}
}
//connect root-root
set<int>s;
for(pair<int,int> it: two){
int pu = findUpar(it.first);
int pv = findUpar(it.second);
if(pu == pv) return 0;
adj[pu][pv] = 1; adj[pv][pu] = 1;
s.insert(pu);
s.insert(pv);
}
if(s.size() < 3 && two.size() != 0) return 0;
//making them the same component
for(pair<int,int> it: two){
U(findUpar(it.first), findUpar(it.second));
}
//check if in the same component (check zero)
for(pair<int,int> it: zero){
if(findUpar(it.first) == findUpar(it.second)) return 0;
}
build(adj); return 1;
}
