#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 42;
bool repr[N];
int n, par[N];
vector<int> cycle[N];
int F(int i) {
if(par[i] == i)
return i;
return par[i] = F(par[i]);
}
void U(int a, int b) {
a = F(a), b = F(b);
if(a != b)
repr[a] = false;
par[a] = b;
}
int construct(vector<vector<int>> p) {
n = p[0].size();
for(int i = 0; i < n; i++) {
par[i] = i;
repr[i] = true;
cycle[i].clear();
}
vector<vector<int>> b(n);
for(int i = 0; i < n; i++)
b[i].resize(n);
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(p[i][j] == 1)
U(i, j);
else 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] != p[F(i)][j])
return 0;
for(int i = 0; i < n; i++)
if(i != F(i))
b[i][F(i)] = 1;
vector<int> rep;
for(int i = 0; i < n; i++)
if(i == par[i])
rep.push_back(i);
for(int i : rep)
for(int j : rep)
if(p[i][j] == 2)
U(i, j);
for(int i : rep)
for(int j : rep)
if(i != j && F(i) == F(j) && p[i][j] != 2)
return 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(F(i) == F(j) && p[i][j] == 0)
return 0;
for(int i : rep)
cycle[F(i)].push_back(i);
for(int i = 0; i < n; i++) {
if(i == par[i]) {
int sz = cycle[i].size();
for(int j = 0; j < sz; j++)
b[cycle[i][j]][cycle[i][(j+1) % sz]] = 1;
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(b[i][j] || b[j][i])
b[i][j] = b[j][i] = 1;
for(int i = 0; i < n; i++)
b[i][i] = 0;
build(b);
return 1;
}
