#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
vector<bool> info(1010);
bool solve(ll n, vector<ll> v, vector<vector<ll>> &p, vector<vector<ll>> &ans){
vector<bool> vis(n);
vector<vector<ll>> c(n);
for(ll i: v) if(!vis[i]){
for(ll j = 0; j < n; j++) if(p[i][j] == 1) c[i].push_back(j), vis[j] = 1;
}
vector<ll> cyc;
for(ll i = 0; i < n; i++) if(c[i].size()) {
if(cyc.size()) ans[cyc.back()][c[i][0]] = ans[c[i][0]][cyc.back()] = 1;
cyc.push_back(c[i][0]); info[c[i][0]] = 1;
for(ll j = 1; j < c[i].size(); j++) ans[c[i][j-1]][c[i][j]] = ans[c[i][j]][c[i][j-1]] = 1;
}
if(cyc.size() > 1) ans[cyc[0]][cyc.back()] = ans[cyc.back()][cyc[0]] = 1;
return 1;
}
bool test(ll n, ll org, ll val, vector<bool> &vis, vector<vector<ll>> &g, vector<vector<ll>> &p){
vis[n] = 1;
for(ll i : g[n]) if(!vis[i]){
if(!info[i]){
if(p[org][i] == 2 || !test(i, org, 1, vis, g, p)) return 0;
}
else{
if((p[org][i] == 1 && val == 2) || !test(i, org, 2, vis, g, p)) return 0;
}
}
return 1;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<bool> vis(n);
vector<vector<ll>> ans(n, vector<ll>(n));
for(ll i = 0; i < n; i++) if(!vis[n]){
vector<ll> comp;
for(ll j = 0; j < n; j++) if(p[i][j]) comp.push_back(j), vis[j] = 1;
solve(n, comp, p, ans);
}
vector<vector<ll>> g(n);
for(ll i = 0; i < n; i++) for(ll j = 0; j < n; j++) if(ans[i][j]) g[i].push_back(j), g[j].push_back(i);
for(ll i = 0; i < n; i++) {
vector<bool> test_vis(n);
if(!test(i, i, 1, vis, g, p)) return 0;
}
build(ans);
return 1;
}
