#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> d1e, d2e, d2b; // DSU1 end, DSU2 end, DSU2 begin
vector<int> DSU1, DSU2;
int goDSU(int a, vector<int> &DSU){
if (a == DSU[a]){
return a;
}
DSU[a] = goDSU(DSU[a], DSU);
return DSU[a];
}
int construct(vector<vector<int>> p) {
int n = p.size();
DSU1.resize(n);
DSU2.resize(n);
d1e.resize(n, -1);
d2b.resize(n, -1);
d2e.resize(n, -1);
for (int i = 0; i < n; i++){
DSU1[i] = i;
DSU2[i] = i;
}
vector<vector<int>> answer(n, vector<int>(n));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (p[i][j] == 3){
return 0;
}
if (p[i][j] == 1){
DSU1[goDSU(i, DSU1)] = goDSU(j, DSU1);
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (p[i][j] != 1 && goDSU(i, DSU1) == goDSU(j, DSU1)){
return 0;
}
}
}
for (int i = 0; i < n; i++){
if (d1e[goDSU(i, DSU1)] == -1){
d1e[goDSU(i, DSU1)] = i;
}else{
answer[d1e[goDSU(i, DSU1)]][i] = 1;
answer[i][d1e[goDSU(i, DSU1)]] = 1;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (p[i][j] == 2){
DSU2[goDSU(goDSU(i, DSU1), DSU2)] = goDSU(goDSU(j, DSU1), DSU2);
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (p[i][j] == 0 && goDSU(goDSU(i, DSU1), DSU2) == goDSU(goDSU(j, DSU1), DSU2)){
return 0;
}
}
}
for (int i = 0; i < n; i++){
if (i != goDSU(i, DSU1))
continue;
if (d2e[goDSU(i, DSU2)] == -1){
d2e[goDSU(i, DSU2)] = i;
d2b[goDSU(i, DSU2)] = i;
}else{
answer[d2e[goDSU(i, DSU2)]][i] = 1;
answer[i][d2e[goDSU(i, DSU2)]] = 1;
d2e[goDSU(i, DSU2)] = i;
}
}
for (int i = 0; i < n; i++){
if (i != goDSU(goDSU(i, DSU1), DSU2)){
continue;
}
if (d2e[i] == d2b[i])
continue;
answer[d2e[i]][d2b[i]] = 1;
answer[d2b[i]][d2e[i]] = 1;
}
build(answer);
return 1;
}
