#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=1005;
ll n;
ll timer1, timer2;
vll adj1[mxN];
vll adj2[mxN];
bool visited[mxN];
vll v1[mxN], v2[mxN];
ll id1[mxN], id2[mxN];
ll ans[mxN][mxN];
void dfs1(ll cur){
if(visited[cur]) return;
visited[cur]=1;
id1[cur]=timer1;
// v1[id1[cur]].pb(cur);
for(auto &it:adj1[cur]){
dfs1(it);
}
}
void dfs2(ll cur){
if(visited[cur]) return;
visited[cur]=1;
id2[cur]=timer2;
v2[id2[cur]].pb(cur);
for(auto &it:adj2[cur]){
dfs2(it);
}
}
void add_edge(ll a, ll b){
ans[a][b]=1;
ans[b][a]=1;
}
}
int construct(vector<vector<int>> p) {
n = p.size();
memset(ans, 0, sizeof(ans));
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
if(i==j) continue;
if(p[i][j]>0){
adj1[i].pb(j);
adj1[j].pb(i);
}
if(p[i][j]==1){
adj2[i].pb(j);
adj2[j].pb(i);
}
}
}
memset(visited, 0, sizeof(visited));
timer1=0;
for(ll i=0;i<n;i++){
if(!visited[i]){
dfs1(i);
timer1++;
}
}
memset(visited, 0, sizeof(visited));
timer2=0;
for(ll i=0;i<n;i++){
if(!visited[i]){
dfs2(i);
timer2++;
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
if(i==j) continue;
if(p[i][j]==3) return 0;
else if(p[i][j]==0){
if(id1[i]==id1[j]) return 0;
}
else if(p[i][j]==2){
if(id2[i]==id2[j]) return 0;
}
else if(p[i][j]==1){
if(id2[i]!=id2[j]) return 0;
}
}
}
for(ll i=0;i<timer2;i++){
v1[id1[v2[i][0]]].pb(v2[i][0]);
for(ll j=1;j<(ll) v2[i].size();j++){
add_edge(v2[i][0], v2[i][j]);
}
}
for(ll i=0;i<timer1;i++){
if((ll) v1[i].size()==1LL) continue;
if((ll) v1[i].size()==2LL) return 0;
for(ll j=0;j<(ll) v1[i].size();j++){
add_edge(v1[i][j], v1[i][(j+1)%((ll) v1[i].size())]);
}
}
vector<vector<int>> re(n, vector<int>(n));
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
re[i][j]=(int) ans[i][j];
}
}
build(re);
return 1;
}
