#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1e3 + 10;
int n, par[N][3];
vector<vector<int>> output;
int root(int v, int id){
return (par[v][id] == -1 ? v : par[v][id] = root(par[v][id], id));
}
void merge(int u, int v, int id){
if ((u = root(u, id)) == (v = root(v, id)))
return ;
par[u][id] = v;
}
int construct(vector<vector<int>> p) {
n = p.size();
output.resize(n);
for (int i = 0; i < n; i++)
output[i].resize(n);
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (p[i][j] == 3)
return 0;
for (int v = 0; v < n; v ++)
par[v][0] = par[v][1] = -1;
for (int i = 0; i < n; i ++){
for (int j = 0; j < n; j ++){
if (p[i][j])
merge(i, j, 0);
if (p[i][j] == 1)
merge(i, j, 1);
}
}
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (p[i][j] == 0 and root(i, 0) == root(j, 0))
return 0;
for (int rr = 0; rr < n; rr ++){
vector<int> comp;
for (int i = 0; i < n; i ++)
if (root(i, 0) == rr)
comp.push_back(i);
if (comp.empty()) continue;
vector<int> roots;
for (int u : comp){
vector<int> small_comp;
for (int v : comp){
if (root(v, 1) == u)
small_comp.push_back(v);
}
if (small_comp.empty()) continue;
roots.push_back(u);
for (int v : small_comp){
if (u != v)
output[u][v] = output[v][u] = 1;
for (int x : comp){
if (root(x, 1) == u){
if (p[x][v] != 1) return 0;
continue;
}
if (p[x][v] != 2) return 0;
}
}
}
int sz = roots.size();
for (int i = 0; i < sz and sz > 2; i ++)
output[roots[i]][roots[(i + 1) % sz]] = output[roots[(i + 1) % sz]][roots[i]] = 1;
if (sz == 2) return 0;
}
build(output);
return 1;
}
