#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define maxn 1010
#define pb push_back
int foi1[maxn];
int rep1[maxn];
int rep2[maxn];
vector<int> L1[maxn];
vector<int> L2[maxn];
vector<int> comp;
void dfs1(int v,int p){
if(foi1[v]) return;
foi1[v] = 1;
rep1[v] = p;
comp.pb(v);
for(int i : L1[v])
dfs1(i,p);
}
int foi2[maxn];
void dfs2(int v,int p){
if(foi2[v]) return;
foi2[v] = 1;
rep2[v] = p;
comp.pb(v);
for(int i : L2[v]){
if(rep1[i] == i)
dfs2(i,p);
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
for(int j=0;j<n;j++){
row[j] = 0;
if(p[i][j] == 1)
L1[i].pb(j);
if(p[i][j] == 2)
L2[i].pb(j);
if(p[i][j] == 3)
return 0;
}
answer.push_back(row);
}
for(int i=0;i<n;i++)
if(!foi1[i]){
comp.clear();
dfs1(i,i);
for(int j=1;j<(int)comp.size();j++)
answer[comp[j-1]][comp[j]] = answer[comp[j]][comp[j-1]] = 1;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(rep1[i] == rep1[j] && p[i][j] != 1)
return 0;
for(int i=0;i<n;i++)
if(!foi2[i] && rep1[i] == i){
comp.clear();
dfs2(i,i);
if(comp.size() == 2) return 0;
if(comp.size() > 1)
for(int j=0;j<(int)comp.size();j++){
int A = comp[j];
int B = comp[(j+1)%comp.size()];
answer[A][B] = answer[B][A] = 1;
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(rep1[i] != rep1[j] && rep2[rep1[i]] == rep2[rep1[j]] && p[i][j] != 2)
return 0;
if(rep1[i] != rep1[j] && rep2[rep1[i]] != rep2[rep1[j]] && p[i][j] != 0)
return 0;
}
build(answer);
return 1;
}
