#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)
using namespace std;
//TODO: SOLUTION
int n;
bool contains3(vvi & paths) {
rep(i, 0, n) {
rep(j, 0, n) {
if (paths[i][j] == 3)
return true;
}
}
return false;
}
bool trees_are_fine(vvi & paths, vi & treeof) {
rep(x, 0, n) {
rep(y, 0, n) {
if (treeof[x] == treeof[y] && paths[x][y] != 1)
return false;
if (treeof[x] != treeof[y] && paths[x][y] == 1)
return false;
}
}
return true;
}
bool trees_connected(vvi & paths, vi & t1, vi & t2) {
for (int x : t1) {
for (int y : t2) {
if (paths[x][y] != 2)
return false;
}
}
return true;
}
bool cycle_contains(vvi & paths, vi & cycle, vvi & trees, vi & tr) {
for (int tidx : cycle) {
auto & cyc_tree = trees[tidx];
if (!trees_connected(paths, cyc_tree, tr))
return false;
}
return true;
}
bool cycles_are_fine(vvi & paths, vi & cycleof, vvi & trees) {
rep(i, 0, trees.size()) {
rep(j, 0, trees.size()) {
if (i == j)
continue;
if (cycleof[i] == cycleof[j] && !trees_connected(paths, trees[i], trees[j]))
return false;
if (cycleof[i] != cycleof[j] && trees_connected(paths, trees[i], trees[j]))
return false;
}
}
return true;
}
bool connect_trees(vvi & gr, vvi & trees) {
for (auto & tr : trees) {
rep(i, 1, tr.size()) {
gr[tr[i]][tr[i - 1]] = gr[tr[i - 1]][tr[i]] = 1;
}
}
return true;
}
bool connect_cycles(vvi & gr, vvi & cycles, vvi & trees) {
for (auto & cyc : cycles) {
if (cyc.size() == 2)
return false;
if (cyc.size() == 1)
continue;
rep(i, 0, cyc.size()) {
int x = cyc[i];
int y = cyc[(i + 1) % cyc.size()];
gr[trees[x][0]][trees[y][0]] = gr[trees[y][0]][trees[x][0]] = 1;
}
}
return true;
}
/*void build(vvi gr) {
rep(i, 0, n) {
rep(j, 0, n) {
cerr << gr[i][j] << ' ';
}
cerr << '\n';
}
}*/
int construct(vvi paths) {
n = paths.size();
// contains 3 => not possible
if (contains3(paths))
return 0;
// construct maximal trees
vvi trees;
vi treeof(n, 0);
rep(x, 0, n) {
bool found_tree = false;
rep(i, 0, trees.size()) {
auto & tr = trees[i];
bool this_tree = true;
for (int y : tr) {
if (paths[x][y] != 1) {
this_tree = false;
break;
}
}
if (this_tree) {
tr.push_back(x);
treeof[x] = i;
found_tree = true;
break;
}
}
if (!found_tree) {
trees.push_back({x});
treeof[x] = trees.size() - 1;
}
}
// check if partition into trees is correct
if (!trees_are_fine(paths, treeof))
return 0;
// form cycles on trees
vvi cycles; // trees are now vertices
vi cycleof(trees.size());
rep(t, 0, trees.size()) {
vi & tr = trees[t];
bool cycle_found = false;
rep(i, 0, cycles.size()) {
auto & cyc = cycles[i];
if (cycle_contains(paths, cyc, trees, tr)) {
cycleof[t] = i;
cyc.push_back(t);
cycle_found = true;
}
}
if (!cycle_found) {
cycles.push_back({t});
cycleof[t] = cycles.size() - 1;
}
}
// validate cycles
if (!cycles_are_fine(paths, cycleof, trees))
return 0;
// construct graph
vvi gr(n, vi(n, 0));
if (!connect_trees(gr, trees))
return 0;
if (!connect_cycles(gr, cycles, trees))
return 0;
// build the graph
rep(i, 0, n) gr[i][i] = 0;
build(gr);
return 1;
}
/*
int main() {
vvi p1 = {{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}};
vvi p2 = {{1, 0}, {0, 1}};
vvi p3 = {
{1, 2, 2, 2, 2, 2, 0, 0, 0, 0},
{2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
{2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
{2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
{2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
{2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1}
};
cout << construct(p1) << endl;
cout << construct(p2) << endl;
cout << construct(p3) << endl;
}*/
