#include "supertrees.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
// void build(vector<vector<int>> b)
// {
// for (auto r : b)
// {
// for (auto c : r)
// cerr << c << " ";
// cerr << '\n';
// }
// cerr << '\n';
// }
const int MX = 1005;
int N;
vector<int> adj[MX];
vector<int> component, vis(MX);
void dfs(int u)
{
// cerr << "dfs on " << u << '\n';
vis[u] = 1;
component.push_back(u);
for (int v : adj[u])
if (!vis[v])
dfs(v);
}
vector<int> tree[MX];
vector<int> vis2(MX), outside_cycle(MX);
vector<bool> in_tree(MX);
void dfs2(int u)
{
// cerr << "doing dfs2 on " << u << '\n';
vis2[u] = 1;
outside_cycle.push_back(u);
for (int v : tree[u])
if (!vis2[v])
dfs2(v);
}
int construct(vector<vector<int>> p)
{
N = p.size();
// cerr << "N = " << N << '\n';
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
if (p[i][j] == 3)
return 0;
if (p[i][j] > 0)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// cerr << "created adjacency list " << '\n';
vector<vector<int>> ans(N, vector<int>(N));
for (int node = 0; node < N; node++)
{
// cerr << "N = " << N << '\n';
// cerr << "node = " << node << '\n';
if (!vis[node])
{
component.clear();
dfs(node);
int n = sz(component);
// cerr << "size of component = n = " << n << '\n';
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int u = component[i], v = component[j];
// cerr << "i = " << i << ", j = " << j << '\n';
if (p[u][v] == 0)
return 0;
if (p[u][v] == 1)
{
tree[u].push_back(v);
tree[v].push_back(u);
}
}
}
// cerr << "tree counting finished\n";
vector<int> cycle;
for (int idx : component)
if (!vis2[idx])
{
outside_cycle.clear();
dfs2(idx);
// cerr << "finished doing dfs2\n";
for (int u : outside_cycle)
in_tree[u] = true;
for (int u : outside_cycle)
{
for (int v : component)
{
if (in_tree[v] && p[u][v] != 1)
{
// cerr << "returning 0" << '\n';
return 0;
}
if (!in_tree[v] && p[u][v] != 2)
{
// cerr << "returning 0" << '\n';
return 0;
}
}
}
for (int i = 0; i < sz(outside_cycle) - 1; i++)
{
int u = outside_cycle[i], v = outside_cycle[i + 1];
ans[u][v] = ans[v][u] = 1;
}
cycle.push_back(outside_cycle[0]);
for (int u : outside_cycle)
in_tree[u] = false;
}
// cerr << "sz(cycle) = " << sz(cycle) << '\n';
if (sz(cycle) == 2)
return 0;
if (sz(cycle) > 2)
{
for (int i = 0; i < sz(cycle); i++)
{
int u = cycle[i], v = cycle[(i + 1 == sz(cycle) ? 0 : i + 1)];
ans[u][v] = ans[v][u] = 1;
}
}
}
}
build(ans);
return 1;
}
// int main()
// {
// int n;
// cin >> n;
// vector<vector<int>> in(n, vector<int>(n));
// for (auto &r : in)
// {
// for (auto &c : r)
// cin >> c;
// }
// for (auto x : in)
// {
// for (auto y : x)
// // cerr << y << " ";
// // cerr << '\n';
// }
// construct(in);
// return 0;
// }
