#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
int construct_forest(const vector<vector<int>>& p) {
int n{int(p.size())};
vector<bool> vis(n);
rep(i, n) if(!vis[i])
rep(j, n)
if(p[i][j]) {
if(p[i] != p[j])
return 0;
vis[j] = true;
}
return 1;
}
vector<vector<int>> build_forest(const vector<vector<int>>& p) {
int n{int(p.size())};
vector<bool> vis(n);
vector<vector<int>> adj(n, vector<int>(n));
rep(i, n) if(!vis[i])
rep(j, n) if(p[i][j] && i != j)
adj[i][j] = adj[j][i] = 1, vis[j] = true;
return adj;
}
int add_cycles(const vector<vector<int>>& p, vector<vector<int>>& adj) {
int n{int(p.size())};
vector<bool> vis(n);
vector<int> tree_head;
vector<int> tree_of(n);
int t{};
rep(i, n) if(!vis[i]) {
tree_head.push_back(i);
rep(j, n) if(p[i][j] == 1)
tree_of[j] = t, vis[j] = true;
++t;
}
rep(i, n) rep(j, n)
if(p[i][j] == 1) assert(tree_of[i] == tree_of[j]);
else assert(tree_of[i] != tree_of[j]);
rep(i, n) rep(j, n)
if(p[i][j] == 2 && p[tree_head[tree_of[i]]][j] != 2)
return 0;
else if(p[tree_head[tree_of[i]]][j] == 2 && p[i][j] != 2)
return 0;
fill(vis.begin(), vis.end(), false);
vector<vector<int>> tree_comp;
for(int i: tree_head) if(!vis[i]) {
tree_comp.emplace_back();
for(int j: tree_head) if(p[i][j] != 0) {
rep(k, n) {
if(p[i][k] == 2 && p[k][j] == 0)
return 0;
else if(p[i][k] == 0 && p[k][j] == 2)
return 0;
vis[j] = true;
}
tree_comp.back().push_back(j);
}
}
for(vector<int>& comp: tree_comp) {
rep(i, int(comp.size())) {
int j = comp[(i + 1) % int(comp.size())];
if(comp[i] != j)
adj[comp[i]][j] = adj[j][comp[i]] = 1;
}
}
return 1;
}
int construct(vector<vector<int>> p) {
int n{int(p.size())};
vector<vector<int>> p2{p};
rep(i, n) rep(j, n) p2[i][j] %= 2;
if(!construct_forest(p2))
return 0;
vector<vector<int>> adj{build_forest(p2)};
if(!add_cycles(p, adj))
return 0;
build(adj);
return 1;
}
