#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/day2/debug.h"
#else
#define debug(...) void(37)
#endif
int construct(std::vector<std::vector<int>> P) {
int N = int(P.size());
vector<vector<int>> ans(N, vector<int>(N));
auto Add = [&](int x, int y) {
ans[x][y] = ans[y][x] = true;
};
bool bad = false;
auto Group = [&](vector<int> s, function<bool(int)> connected) {
int c = int(s.size());
vector<int> used(c, -1);
vector<vector<int>> gs;
for (int i = 0; i < c; ++i) {
if (used[i] != -1) {
continue;
}
used[i] = i;
gs.push_back({s[i]});
for (int j = i + 1; j < c; ++j) {
if (connected(P[s[i]][s[j]])) {
if (used[j] != -1) {
bad = true;
}
used[j] = i;
gs.back().push_back(s[j]);
}
}
}
for (int i = 0; i < c; ++i) {
for (int j = 0; j < c; ++j) {
bad |= connected(P[s[i]][s[j]]) != (used[i] == used[j]);
}
}
return gs;
};
vector<int> foo(N);
iota(foo.begin(), foo.end(), 0);
auto gs = Group(foo, [&](int x) {
return x != 0;
});
debug(gs);
for (auto g : gs) {
bool two = false, three = false;
for (auto x : g) {
for (auto y : g) {
two |= P[x][y] == 2;
three |= P[x][y] == 3;
}
}
auto ones = Group(g, [&](int x) {
return x == 1;
});
if ((two && three) || (two && int(ones.size()) < 3) || (three && int(ones.size()) < 4)) {
bad = true;
break;
}
for (auto o : ones) {
for (int i = 0; i < int(o.size()) - 1; ++i) {
Add(o[i], o[i + 1]);
}
}
for (int i = 0; i < int(ones.size()) - 1; ++i) {
Add(ones[i][0], ones[i + 1][0]);
}
if (two || three) {
Add(ones[0][0], ones.back()[0]);
}
if (three) {
Add(ones[0][0], ones[2][0]);
}
}
if (bad) {
return 0;
}
build(ans);
return 1;
}
