#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
void build(std::vector<std::vector<int>> _b);
vector<int>par;
vector<int>cpar;
int UF(int u) {
if(par[u] == u)
return u;
return par[u] = UF(par[u]);
}
int CUF(int u) {
if(cpar[u] == u)
return u;
return cpar[u] = UF(cpar[u]);
}
int construct(vector<vector<int>> p) {
int n = p.size();
par.resize(n);
cpar.resize(n);
vector<bool>has_cycle(n,0);
for(int i = 0 ; i < n ; i++)
par[i] = cpar[i] = i;
bool ok = 1;
vector<vector<int>>ans(n, vector<int>(n,0));
for(int i = 0 ; i < n ; i++) {
for(int j = i+1 ; j < n ; j++) {
if(p[i][j] == 3)
ok = 0;
if(p[i][j] == 1) {
int A = UF(i), B = UF(j);
if(A == B)
continue;
ans[i][j] = ans[j][i] = 1;
par[A] = B;
}
if(p[i][j] == 2) {
int A = CUF(i), B = CUF(j);
if(A == B)
continue;
cpar[A] = B;
}
}
}
for(int i = 0 ; i < n ; i++) {
for(int j = i+1 ; j < n ; j++) {
int A = UF(i), B = UF(j);
if(A == B && p[i][j] != 1)
ok = 0;
A = CUF(i), B = CUF(j);
if(A == B)
has_cycle[UF(i)] = has_cycle[UF(j)] = 1;
if(A == B && p[i][j] != 2)
ok = 0;
}
}
for(int i = 0 ; i < n ; i++) {
for(int j = i+1 ; j < n ; j++) {
if(p[i][j] == 0 && has_cycle[UF(i)])
ok = 0;
}
}
for(int i = 0 ; i < n ; i++) {
if(CUF(i) != i)
continue;
int f = -1, l = -1;
for(int j = 0 ; j < n ; j++) {
if(CUF(j) == i) {
if(f == -1)
f = j;
if(l != -1)
ans[l][j] = ans[j][l] = 1;
l = j;
}
}
if(f == l)
continue;
ans[l][f] = ans[f][l] = 1;
}
if(ok) {
build(ans);
return 1;
}
return 0;
}
