#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];
s[a] = 0;
}
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 && getpar(i) != getpar(j)) {
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++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1 && getpar(i) != getpar(j)) return 0;
}
}
for (int i = 0; i < n; i++) {
if (getpar(i) != i) continue;
vector <int> cnt(n+2,0);
for (auto x:v[i]) {
for (int j = 0; j < n; j++) {
if (p[x][j] == 2 && p[j][x] == 2) cnt[j]++;
}
}
for (int j = 0; j < n; j++) {
if (!(cnt[j] == 0 || cnt[j] == s[i])) return 0;
}
}
vector <int> root;
for (int i = 0; i < n; i++) {
if (getpar(i) == i) root.push_back(i);
}
for (int i = 0; i < n; i++) {
par[i] = i;
s[i] = 1;
v[i].clear();
}
for (auto x:root) {
for (auto y:root) {
if (p[x][y] == 2) unionset(x,y);
}
}
for (auto x:root) {
v[getpar(x)].push_back(x);
}
for (auto x:root) {
if (x != getpar(x)) continue;
for (auto a:v[x]) {
for (auto b:v[x]) {
if (a != b && p[a][b] != 2) return 0;
}
}
for (int i = 0; i < v[x].size(); i++) {
add(v[x][i],v[x][(i+1)%v[x].size()]);
}
}
for (int i = 0; i < n; i++) answer[i][i] = 0;
build(answer);
return 1;
}
