#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> pa;
vector<int> pa1;
int f(int x){
if (pa[x]==x) return x;
return pa[x] = f(pa[x]);
}
int f1(int x){
if (pa1[x]==x) return x;
return pa1[x] = f1(pa1[x]);
}
void u1(int x, int y){
if (f1(x)==f1(y)) return;
pa1[f1(x)] = f1(y);
}
void u(int x, int y){
if (f(x)==f(y)) return;
pa[f(x)] = f(y);
}
vector<vector<int> >twos;
int construct(std::vector<std::vector<int> > p) {
int n = p.size();
for (int i = 0;i<n;i++) {pa.push_back(i);pa1.push_back(i);}
vector<vector<int> > ans;
ans.resize(n);
twos.resize(n);
for (int i = 0;i<n;i++) ans[i].assign(n,0);
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
if (p[i][j]==1 and f(i)!=f(j)) {u(f(i),f(j));}
if (p[i][j]!=0 and f1(i)!=f1(j)) {u1(f1(i),f1(j));}
if (p[i][j]==3) return 0;
}
}
for (int i = 0;i<n;i++){
twos[f1(i)].push_back(i);
}
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
if (p[i][j]==0 and (f(i)==f(j) or (f1(i)==f1(j)))) {return 0;}
}
}
for (int i = 0;i<n;i++){
vector<int> ones;
vector<int> cycles;
ones.assign(n,-1);
int p = -1;
for (int j = 0;j<twos[i].size();j++){
if (ones[f(twos[i][j])]==-1){
cycles.push_back(twos[i][j]);
ones[f(twos[i][j])] = twos[i][j];
}
else {
ans[ones[f(twos[i][j])]][twos[i][j]] = 1;
ans[twos[i][j]][ones[f(twos[i][j])]] = 1;
ones[f(twos[i][j])] = twos[i][j];
}
}
if (cycles.size()<2) continue;
if (cycles.size()==2) return 0;
for (int i = 0;i<cycles.size()-1;i++) {
ans[cycles[i]][cycles[i+1]] = 1;
ans[cycles[i+1]][cycles[i]] = 1;
}
ans[cycles[cycles.size()-1]][cycles[0]] = 1;
ans[cycles[0]][cycles[cycles.size()-1]] = 1;
}
build(ans);
return 1;
}
