#include "supertrees.h"
#include<iostream>
#include <vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
const int MAXN = 1010;
int n;
bool vi1[MAXN], vi2[MAXN], ad1[MAXN][MAXN], ad2[MAXN][MAXN];
vector<int> comp;
void dfs(int v, bool* vis, bool adj[][MAXN]){
vis[v]=true;
comp.PB(v);
forn(i, n) if(!vis[i] && adj[v][i]) dfs(i, vis, adj);
}
bool check(vector<int>& com, bool adj[][MAXN]){
bool ret = true;
int sz = (int)com.size();
forn(i, sz) forsn(j, i+1, sz) ret &= adj[com[i]][com[j]];
return ret;
}
int construct(std::vector<std::vector<int>> p) {
n = (int)p.size();
std::vector<std::vector<int>> ans(n, vector<int>(n, 0));
bool has3 = false;
forn(i, n) forn(j, n) has3 |= (p[i][j] == 3);
if(has3) return 0;
forn(i, n) forn(j, n) ad1[i][j] = (p[i][j] > 0);
forn(i, n) forn(j, n) ad2[i][j] = (p[i][j] == 1);
forn(i, n) if(!vi1[i]){
dfs(i, vi1, ad1);
if(!check(comp, ad1)) return 0;
vector<int> al, rep;
swap(comp, al);
for(int el:al) if(!vi2[el]){
dfs(el, vi2, ad2);
if(!check(comp, ad2)) return 0;
forn(j, comp.size() - 1) ans[comp[j]][comp[j+1]]=ans[comp[j+1]][comp[j]]=1;
rep.PB(comp.back());
comp.clear();
}
if((int)rep.size() == 2) return 0;
if((int)rep.size() > 2){
forn(j, rep.size() - 1) ans[rep[j]][rep[j+1]]=ans[rep[j+1]][rep[j]]=1;
ans[rep.front()][rep.back()]=ans[rep.back()][rep.front()]=1;
}
}
build(ans);
return 1;
}
