#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[1001];
int par(int x) {
if(dsu[x]==x) return x;
return dsu[x] = par(dsu[x]);
}
int dsu2[1001];
int par2(int x) {
if(dsu2[x]==x) return x;
return dsu2[x] = par2(dsu2[x]);
}
vector<int> cyc[1001];
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n, 0));
for(int i=0;i<n;i++) dsu[i] = dsu2[i] = i;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) {
if(p[i][j]==3) return 0;
if(p[i][j]==1) {
int pari = par(i);
int parj = par(j);
if(pari!=parj) {
dsu[pari] = parj;
answer[pari][parj] = answer[parj][pari] = 1;
}
}
}
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) {
if(p[i][j]==2) {
int pari = par2(par(i));
int parj = par2(par(j));
if(pari!=parj) {
dsu2[pari] = parj;
}
}
}
for(int i=0;i<n;i++) {
if(par(i)==i) cyc[par2(i)].push_back(i);
}
for(int i=0;i<n;i++) {
if(cyc[i].size()<=1) continue;
if(cyc[i].size()==2) return 0;
int last = cyc[i][cyc[i].size()-1];
for(int cur:cyc[i]) {
answer[last][cur] = answer[cur][last] = 1;
last = cur;
}
}
for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
if(!p[i][j]) {
int pari = par(i);
int parj = par(j);
if(pari==parj || par2(pari)==par2(parj)) {
return 0;
}
}
}
build(answer);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
