#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1001;
int n , comp[N] , par[N];
vector < vector < int > > res;
vector < int > G[N] , C[N] , F[N];
bool vis[N];
int cur_comp = 0;
void add_edge(int ii , int jj , bool g){
if(!g){
res[ii][jj] = 1;
res[jj][ii] = 1;
}
else{
G[ii].push_back(jj);
G[jj].push_back(ii);
}
}
void dfs(int v){
comp[v] = cur_comp;
C[cur_comp].push_back(v);
vis[v] = 1;
for(int u : G[v]){
if(!vis[u]) dfs(u);
}
}
bool used[N];
vector < int > nodes;
vector < vector < int > > all;
void DFS(int v){
nodes.push_back(v);
used[v] = 1;
for(int u : F[v])
{
if(!used[u]) DFS(u);
}
}
bool ok(vector < vector < int > > p){
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(p[i][j] == 2 && par[i] == par[j] && par[i] != -1 && par[j] != -1) return false;
if(p[i][j] > 0 && (comp[i] != comp[j])) return false;
if(p[i][j] == 0 && (comp[i] == comp[j])) return false;
if(p[i][j] == 2)
{
if(C[comp[i]].size() == 2) return false;
}
}
}
return true;
}
int construct(vector < vector < int > > p)
{
n = p.size();
for(int i = 0;i < n;i++) par[i] = -1;
res.assign(n , vector < int > (n));
for(int i = 0;i < n - 1;i++){
for(int j = i + 1;j < n;j++){
if(p[i][j] > 0){
add_edge(i , j , 1);
if(p[i][j] == 1){
F[i].push_back(j);
F[j].push_back(i);
}
}
}
}
for(int i = 0;i < n;i++)
{
if(!vis[i]) ++cur_comp , dfs(i);
}
for(int i = 1;i <= cur_comp;i++)
{
bool cont3 = 0;
for(int node1 : C[i]) for(int node2 : C[i]) cont3 |= (p[node1][node2] == 3);
if(!cont3){
all.clear();
for(int node : C[i])
{
if(!used[node])
{
nodes.clear();
DFS(node);
all.push_back(nodes);
}
}
if(all.size() == 1){
for(int j = 0;j < all[0].size() - 1;j++) add_edge(all[0][j] , all[0][j + 1] , 0);
continue;
}
else{
for(int j = 0;j < all.size();j++){
for(int ii = 0;ii < all[j].size() - 1;ii++) add_edge(all[j][ii] , all[j][ii + 1] , 0);
}
for(int j = 0;j < all.size();j++){
for(int ii = 0;ii < all[j].size();ii++) par[all[j][ii]] = all[j][0];
}
for(int j = 0;j < all.size() - 1;j++) add_edge(all[j][0] , all[j + 1][0] , 0);
add_edge(all[0][0] , all[all.size() - 1][0] , 0);
}
}
else{
all.clear();
for(int node : C[i])
{
if(!used[node])
{
nodes.clear();
DFS(node);
if(nodes.size() > 1) all.push_back(nodes);
}
}
if(all.size() != 1) return 0;
for(int j = 0;j < all[0].size() - 1;j++) add_edge(all[0][j] , all[0][j + 1] , 0);
vector < bool > usd(n , false);
for(int node : all[0]) usd[node] = 1;
vector < int > f1 , f2;
for(int node : C[i]){
if(!usd[node]){
for(int j = 0;j < n;j++){
if(usd[j]) continue;
if(p[node][j] == 2 or node == j) f1.push_back(j);
else if(p[node][j] == 3) f2.push_back(j);
}
break;
}
}
if(f1.size() <= 1) return 0;
if(f2.size() <= 1) return 0;
for(int j = 0;j < f1.size() - 1;j++) add_edge(f1[j] , f1[j + 1] , 0);
for(int j = 0;j < f2.size() - 1;j++) add_edge(f2[j] , f2[j + 1] , 0);
add_edge(all[0][0] , f1[0] , 0);
add_edge(all[0][0] , f1[f1.size() - 1] , 0);
add_edge(all[0][all[0].size() - 1] , f2[0], 0);
add_edge(all[0][all[0].size() - 1] , f2[f2.size() - 1] , 0);
}
}
if(!ok(p)) return 0;
build(res);
return 1;
}
