#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector < int > pr, rk;
int N;
dsu(){}
dsu(int n):N(n){
pr.resize(N), rk.resize(N);
for(int i = 0; i < N; ++i) pr[i] = i, rk[i] = 1;
}
inline int get(int x){
return x == pr[x] ? x : pr[x] = get(pr[x]);
}
inline bool unite(int x, int y){
x = get(x), y = get(y);
if(x != y){
if(rk[x] < rk[y]) swap(x, y);
pr[y] = x, rk[x] += rk[y];
return true;
}
return false;
}
}all(1004), one(1004);
vector < int > circle[1004], line[1004];
int construct(std::vector<std::vector<int>> p) {
int N = p.size();
std::vector<std::vector<int>> answer;
answer.resize(N);
for(int i = 0; i < N; ++i){
answer[i].resize(N);
for(int j = 0; j < N; ++j){
if(p[i][j] == 3){
return 0;
}
if(p[i][j]){
all.unite(i, j);
}
if(p[i][j] == 1){
one.unite(i, j);
}
}
}
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
if(!p[i][j] && all.get(i) == all.get(j)) return 0;
if(p[i][j] == 2 && one.get(i) == one.get(j)) return 0;
}
}
for(int i = 0; i < N; ++i){
if(one.get(i) == i){
circle[all.get(i)].push_back(i);
}
line[one.get(i)].push_back(i);
}
for(int i = 0; i < N; ++i){
if((int)circle[i].size() == 2){
return 0;
}
for(int j = 0; j < (int)circle[i].size() - 1; ++j){
answer[circle[i][j]][circle[i][j + 1]] = answer[circle[i][j + 1]][circle[i][j]] = 1;
}
if((int)circle[i].size() >= 3){
answer[circle[i][0]][circle[i].back()] = answer[circle[i].back()][circle[i][0]] = 1;
}
for(int j = 0; j < (int)line[i].size() - 1; ++j){
answer[line[i][j]][line[i][j + 1]] = answer[line[i][j + 1]][line[i][j]] = 1;
}
}
build(answer);
return 1;
}
