/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
Music: https://www.youtube.com/watch?v=mewNjPCi76E&list=RDmewNjPCi76E&start_radio=1, https://www.youtube.com/watch?v=9ZEURntrQOg&list=RDMM&start_radio=1&rv=ePtFpGENP8s, https://www.youtube.com/watch?v=L_BPzUfFHpQ
*/
#include "supertrees.h"
#include <cassert>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
struct DSU {
vector<int> par;
int n, components;
DSU(int _n) {
n = _n;
components = n;
par.assign(n, -1);
}
DSU() {
}
void init(int _n) {
n = _n;
components = _n;
par.assign(_n, -1);
}
int Find(int u) {
if (par[u] < 0)
return u;
return par[u] = Find(par[u]);
}
bool Union(int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) {
components--;
if (par[u] > par[v]) {
swap(u, v);
}
par[u] += par[v];
par[v] = u;
return true;
} else {
return false;
}
}
};
vector<vector<int>> adj, _p, matrixr;
vector<char> inChain, inCycle, used; // chars
DSU t;
int _n;
void connect(const int &u, const int &v) {
adj[v].push_back(u);
adj[u].push_back(v);
matrixr[u][v] = true;
matrixr[v][u] = true;
}
void init() {
dbg("init");
_n = _p.size();
assert(_p[0].size() == _n);
inChain.assign(_n, false);
inCycle.assign(_n, false);
used.assign(_n, false);
adj.resize(_n);
matrixr.assign(_n, vector<int>(_n, false));
t.init(_n);
for (int i = 0; i < _n; i++) {
for (int j = i + 1; j < _n; j++) {
if (_p[i][j] != 0)
t.Union(i, j);
if (_p[i][j] == 1) {
inChain[i] = true;
inChain[j] = true;
}
if (_p[i][j] == 2) {
inCycle[i] = true;
inCycle[j] = true;
}
}
}
dbg("Init is over");
}
char solve() {
for (int v = 0; v < _n; v++) {
if (used[v])
continue;
// INFO: Chain is completly true
if (inChain[v] == true && inCycle[v] == false) {
vector<int> chain;
chain.push_back(v);
used[v] = true;
for (int u = 0; u < _n; u++) {
if (u == v)
continue;
if (_p[u][v] == 1) {
// assert(_p[v][u] == 1);
used[u] = true;
chain.push_back(u);
} else {
// assert(_p[v][u] == 0);
}
}
// dbg(chain);
for (int i = 1; i < chain.size(); i++) {
const int &u = chain[i];
const int &v = chain[i - 1];
connect(u, v);
}
continue;
}
if (inCycle[v] == true) {
vector<int> cycle;
cycle.push_back(v);
used[v] = true;
for (int u = 0; u < _n; u++) {
if (u == v)
continue;
if (_p[u][v] == 2) {
used[u] = true;
cycle.push_back(u);
}
}
dbg(cycle);
for (int i = 1; i < cycle.size(); i++) {
const int &u = cycle[i];
const int &v = cycle[i - 1];
connect(u, v);
}
// Make cycle fully
connect(cycle.back(), cycle[0]);
for (int i = 0; i < cycle.size(); i++) {
const int &v = cycle[i];
if (inChain[v] == true) {
vector<int> chain;
int lst = v;
for (int u = 0; u < _n; u++) {
if (u == v)
continue;
if (_p[u][v] == 1) {
used[u] = true;
connect(lst, u);
lst = u;
}
}
}
}
}
}
return 0;
}
char check_answer() {
dbg("Check_answer started");
for (int u = 0; u < _n; u++) {
for (int v = 0; v < _n; v++) {
if (_p[u][v] != _p[v][u])
return false; // INFO: undirected graph
}
}
vector<char> vis(_n, false);
vector<vector<int>> matrixc(_n, vector<int>(_n, false));
int st = -1;
function<void(int, int)> dfs = [&](int v, int pa) {
vis[v] = true;
for (const int &u : adj[v]) {
if (u == pa)
continue;
if (vis[u])
continue;
matrixc[st][u]++;
dfs(u, v);
}
vis[v] = false;
};
for (int i = 0; i < _n; i++) {
st = i;
vis.assign(_n, false);
dfs(i, -1);
}
dbg(_p);
dbg(matrixc);
for (int i = 0; i < _n; i++) {
for (int j = 0; j < _n; j++) {
if (i == j)
continue;
if (_p[i][j] != matrixc[i][j])
return false;
}
}
return true;
}
int answer() {
dbg("answering started");
if (!(check_answer()))
return false;
build(matrixr);
return true;
}
// Attack on titan<3
int construct(std::vector<std::vector<int>> p) {
_p = p;
init();
if (solve())
return 0;
return answer();
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
