#include <bits/stdc++.h>
#include "supertrees.h"
#include <vector>
using namespace std;
const int N = 1e3+5;
int par[N];
int s[N];
vector <vector<int>> v(N);
vector<vector<int>> answer;
int getpar(int x) {
if (x == par[x]) return x;
return par[x] = getpar(par[x]);
}
void unionset(int a, int b) {
a = getpar(a);
b = getpar(b);
if (a == b) {
return;
}
par[a] = b;
s[b] += s[a];
}
void add(int x, int y) {
answer[x][y] = answer[y][x] = 1;
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
vector<int> row(n,0);
answer.push_back(row);
}
for (int i = 0; i < n; i++) s[i] = 1,par[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1) {
unionset(i,j);
add(i,j);
}
}
}
for (int i = 0; i < n; i++) {
v[getpar(i)].push_back(i);
}
for (int i = 0; i < n; i++) {
if (getpar(i) != i) continue;
for (auto x:v[i]) {
for (auto y:v[i]) {
if (p[x][y] != 1) return 0;
}
}
}
for (int i = 0; i < n; i++) {
if (getpar(i) != i) continue;
vector <int> cnt(n,0);
for (auto x:v[i]) {
for (int j = 0; j < n; j++) {
if (p[x][j] == 2) cnt[j]++;
}
}
for (int j = 0; j < n; j++) {
if (!(cnt[j] == 0 || cnt[j] == s[i])) return 0;
}
}
vector <int> fix(n,0);
for (int i = 0; i < n; i++) {
if (getpar(i) != i || fix[getpar(i)]) continue;
vector <int> res(1,i);
fix[i] = 1;
for (int j = 0; j < n; j++) {
if (p[i][j] == 2 && fix[getpar(j)] == 0) res.push_back(getpar(j)),fix[getpar(j)] = 1;
}
res.push_back(i);
for (int j = 0; j < (res).size()-1; j++) {
add(res[j],res[j+1]);
}
}
build(answer);
return 1;
}
