#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1003;
int n;
vector<vector<int>> p, b;
vector<int> V;
int mark[MXN];
void dfs1(int v) {
mark[v] = 1;
V.push_back(v);
for(int u=0; u<n; u++)
if(p[v][u] && !mark[u])
dfs1(u);
}
vector<int> V2;
void dfs2(int v) {
mark[v] = 2;
V2.push_back(v);
for(int u=0; u<n; u++)
if(p[v][u]==1 && mark[u]==1)
dfs2(u);
}
bool solve() {
for(int v : V)
for(int u : V)
if(p[v][u]==0)
return 0;
vector<int> vec;
for(int v : V)
if(mark[v]==1) {
V2.clear();
dfs2(v);
for(int i : V2)
for(int j : V2)
if(p[i][j]==2)
return 0;
vec.push_back(v);
for(int i=0; i+1<V2.size(); i++)
b[V2[i]][V2[i+1]] = b[V2[i+1]][V2[i]] = 1;
}
if(vec.size()==1) return 1;
if(vec.size()==2) return 0;
for(int i=0; i+1<vec.size(); i++)
b[vec[i]][vec[i+1]] = b[vec[i+1]][vec[i]] = 1;
b[vec[0]][vec.back()] = b[vec.back()][vec[0]] = 1;
return 1;
}
int construct(vector<vector<int>> p) {
::p = p;
n = p.size();
b = vector<vector<int>>(n, vector<int>(n, 0));
for(auto &i: p)
for(int j : i)
if(j==3)
return 0;
for(int v=0; v<n; v++)
if(!mark[v]) {
V.clear();
dfs1(v);
if(!solve()) return 0;
}
build(b);
return 1;
}
