#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n;
vector<vector<int>> G;
bool vis[maxn];
bool inloop[maxn];
int belong[maxn];
vector<int> nodes;
void dfs(int u) {
vis[u] = true;
nodes.push_back(u);
for (int v=0;v<n;v++) if (G[u][v] && !vis[v]) dfs(v);
}
void dfs2(int u, int rt) {
vis[u] = true, belong[u] = rt;
for (int v=0;v<n;v++) if (G[u][v] == 1 && !vis[v]) dfs2(v, rt);
}
int construct(vector<vector<int>> p) {
n = p.size();
G = p;
vector<vector<int>> ans(n, vector<int>(n));
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (G[i][j] == 3) return 0;
for (int i=0;i<n;i++) belong[i] = -1;
for (int i=0;i<n;i++) if (!vis[i]) {
nodes.clear();
dfs(i);
for (int u:nodes) vis[u] = false;
vector<int> loop;
for (int u:nodes) if (!vis[u]) {
inloop[u] = true;
loop.push_back(u);
dfs2(u, u);
}
// cout << i << endl;
// for (int u:nodes) cout << u << " "; cout << endl;
// for (int u:loop) cout << u << " "; cout << endl;
int sz = loop.size();
if (sz == 2) return false;
if (sz > 2) {
for (int j=0;j<sz;j++) ans[loop[j]][loop[(j+1)%sz]] = ans[loop[(j+1)%sz]][loop[j]] = 1;
}
for (int u:nodes) if (!inloop[u]) {
bool done = false;
for (int v:nodes) if (inloop[v] && G[u][v] == 1) {
if (done) return 0;
done = true;
ans[u][v] = ans[v][u] = 1;
belong[u] = v;
}
}
for (int u:nodes) if (!inloop[u]) for (int v:nodes) if (!inloop[v]) {
if (G[u][v] == 1 && belong[u] != belong[v]) return 0;
}
}
build(ans);
return 1;
}
