#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC("o3, unroll-loops")
using namespace std;
typedef int ll;
inline 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]);
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;
vector<map<ll, bool>> same_line(n);
for(ll i = 0; i < n; i++) {
for(ll x: c[i]) for(ll y: c[i]) same_line[x][y] = 1;
}
for(ll i : v){
for(ll j = 0; j < n; j++) {
if(p[i][j] == 0){
if(vis[j]) return 0;
}
if(p[i][j] == 1){
if(!same_line[i][j]) return 0;
}
if(p[i][j] == 2){
if(same_line[i][j] || !vis[j]) 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;
if(!solve(n, comp, p, ans)) return 0;
}
build(ans);
return 1;
}
