#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++) {
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> 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;
vector <int> cur(n,0);
cur[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,cur[getpar(i)] = 1;
}
res.push_back(i);
for (int j = 0; j < (res).size()-1; j++) {
add(res[j],res[j+1]);
}
// for (auto x:res) {
// for (auto y:res) {
// if (x == y) continue;
// if (p[x][y] != 2) return 0;
// }
// }
for (auto x:res) {
for (int j = 0; j < n; j++) {
if (getpar(j) == x) continue;
if (p[x][j] == 2 && cur[getpar(j)] == 0) return 0;
}
}
}
for (int i = 0; i < n; i++) answer[i][i] = 0;
build(answer);
return 1;
}
