#include "bits/stdc++.h"
#include "supertrees.h"
#define pb push_back
using namespace std;
vector<int> par, par2;
vector<vector<int> > group;
int fnd(int a){
if(a == par[a]) return a;
else return fnd(par[a]);
}
void merge(int a, int b){
a = fnd(a);
b = fnd(b);
if(a == b) return;
if(group[a].size() > group[b].size()){
par[b] = a;
for(auto itr: group[b]){
group[a].pb(itr);
}
group[b].clear();
}
else{
swap(a, b);
par[b] = a;
for(auto itr: group[b]){
group[a].pb(itr);
}
group[b].clear();
}
}
int fnd2(int a){
if(a == par2[a]) return a;
else return par2[a] = fnd2(par2[a]);
}
void merge2(int a, int b){
a = fnd2(a);
b = fnd2(b);
if(a == b) return;
par2[b] = a;
}
int construct(vector<vector<int>> p) {
int n = p.size();
par.resize(n);
group.resize(n);
for(int i = 0; i < n; i++){
par[i] = i;
group[i].pb(i);
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j] > 0) merge(i, j);
}
}
bool pos = 1;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j] == 0 && fnd(i) == fnd(j)){
pos = 0;
}
}
}
if(!pos){
return 0;
}
vector<vector<int> > ans(n, vector<int>(n, 0));
vector<int> cand(n, -1);
par2.resize(n);
for(int i = 0; i < n; i++){
par2[i] = i;
}
bool pos2 = 1;
for(int i = 0; i < n; i++){
if(par[i] != i) continue;
for(int j = 0; j < group[i].size(); j++){
for(int k = j+1; k < group[i].size(); k++){
int aj = group[i][j], ak = group[i][k];
if(p[aj][ak] == 1){
merge2(aj, ak);
}
}
}
for(int j = 0; j < group[i].size(); j++){
for(int k = j+1; k < group[i].size(); k++){
int aj = group[i][j], ak = group[i][k];
if(p[aj][ak] == 2 && fnd2(aj) == fnd2(ak)){
pos2 = 0;
}
}
}
vector<int> gstart;
for(int j = 0; j < group[i].size(); j++){
int aj = group[i][j];
int gaj = fnd2(aj);
if(cand[gaj] == -1){
cand[gaj] = aj;
gstart.pb(aj);
}
else{
ans[cand[gaj]][aj] = ans[aj][cand[gaj]] = 1;
cand[gaj] = aj;
}
}
for(int j = 1; j < gstart.size(); j++){
ans[gstart[j]][gstart[j-1]] = ans[gstart[j-1]][gstart[j]] = 1;
}
if(gstart.size() > 1){
ans[gstart[0]][gstart[gstart.size()-1]] = ans[gstart[gstart.size()-1]][gstart[0]] = 1;
}
}
if(!pos2){
return 0;
}
build(ans);
return 1;
}
