#include "supertrees.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool same(int a,int b){
return find(a)==find(b);
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
return true;
}
};
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
DSU dsu(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]>0) dsu.unite(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if((p[i][j]==0 and dsu.same(i,j)) or (p[i][j]>0 and !dsu.same(i,j))){
return 0;
}
}
}
vector<vector<int>> a(n);
for(int i=0;i<n;i++){
a[dsu.find(i)].push_back(i);
}
vector<vector<int>> b(n,vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
b[i][j]=0;
}
}
auto add=[&](int x,int y){
b[x][y]=1;
b[y][x]=1;
};
for(int i=0;i<n;i++){
if((int)a[i].size()<=1) continue;
for(int j=0;j<(int)a[i].size()-1;j++){
add(a[i][j],a[i][j+1]);
}
if(p[a[i][0]][a[i][1]]==2) add(a[i].back(),a[i][0]);
}
build(b);
return 1;
}
