#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)
class DSU{
int sz[1000000];
int parent[1000000];
int n;
public:
void init(int N){
n=N;
rep(i,0,n)sz[i]=1,parent[i]=i;
}
int root(int x){
if(x==parent[x])return x;
parent[x]=root(parent[x]);
return parent[x];
}
void merge(int a, int b){
a=root(a);
b=root(b);
if(a==b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a]+=sz[b];
parent[b]=a;
}
};
DSU D;
DSU D2;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
D.init(n);
rep(i,0,n){
rep(j,0,n){
if(p[i][j]==1)D.merge(i,j);
}
}
rep(i,0,n){
bool B=true;
rep(j,i+1,n){
if(D.root(j)==D.root(i)){
B=false;
if(p[i][j]!=1){
return 0;
}
}
}
if(B){
rep(j,0,i){
if(D.root(j)==D.root(i))answer[i][j]=1,answer[j][i]=1;
}
}
}
build(answer);
return 1;
}
