#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
int N, P[2][MAXN];
vector<int> C[MAXN];
vector<vector<int>> ans;
int find(int t,int x) {
if (P[t][x] == x) {
return x;
}
return P[t][x] = find(t,P[t][x]);
}
void join(int t,int x,int y) {
x = find(t,x);
y = find(t,y);
P[t][x] = y;
}
int construct(vector<vector<int>> D) {
N = D.size();
vector<int>row(N);
for (int i=0;i<N;i++) {
ans.push_back(row);
P[0][i] = P[1][i] = i;
}
for (int i=0;i<N;i++) {
for (int j=0;j<i;j++) {
if (D[i][j] == 3) {
return 0;
}
if (D[i][j]) {
join(D[i][j]-1,i,j);
}
}
}
for (int i=0;i<N;i++) {
for (int j=0;j<i;j++) {
if (find(0,i) == find(0,j)) {
if (D[i][j] != 1) {
return 0;
}
}
else if (find(1,i) == find(1,j)) {
if (D[i][j] != 2) {
return 0;
}
}
}
}
for (int i=0;i<N;i++) {
if (find(0,i) == i) {
C[find(1,i)].push_back(i);
}
else {
ans[i][find(0,i)] = ans[find(0,i)][i] = 1;
}
}
for (int i=0;i<N;i++) {
if (C[i].size() < 2) {
continue;
}
if (C[i].size() == 2) {
return 0;
}
for (int j=1;j<(int)C[i].size();j++) {
ans[C[i][j]][C[i][j-1]] = ans[C[i][j-1]][C[i][j]] = 1;
}
ans[C[i].back()][C[i][0]] = ans[C[i][0]][C[i].back()] = 1;
}
build(ans);
return 1;
}
