#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i < e; i++)
#define pr(x) cout << x << endl
#define wpr(x) cout << #x << "=" << x << endl
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
template<class A>
ostream &operator<<(ostream &os, const vector<A> &arr) {
if (arr.empty()) {
return os << "[]";
}
os << "[";
rep(i, 0, arr.size()) {
os << arr[i] << ",]"[i == arr.size() - 1];
}
return os;
}
template<class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
return os << "{" << p.first << "," << p.second << "}";
}
/**
* Solution:
* 1. First split to C.Cs, and check validity.
* 2. For each C.C:
* 1. Find cliques of 1's.
* 2. Create lines of all of those cliques.
* 3. Merge them using a representor to a circle, if there are at least 3 lines.
*
*/
bool handle_comp(vvi &p, vvi &g, vi &comp) {
int sz = comp.size();
if (sz == 0) return 1;
vi color(sz, -1);
int cur_col = 0;
vvi cc;
rep(i, 0, sz) {
if (color[i] >= 0) continue;
color[i] = cur_col++;
cc.push_back({comp[i]});
rep(j, i+1, sz) {
if (p[comp[i]][comp[j]] == 1) {
if (color[j] >= 0) return 0;
color[j] = color[i];
cc.back().push_back(comp[j]);
}
}
}
assert(cur_col <= sz);
int valid = 1;
rep(i, 0, sz) {
rep(j, 0, sz) {
int u = comp[i], v = comp[j];
// If they are in the same C.C, p should be 1. Otherwise, 2.
if (color[i] == color[j]) {
valid &= (p[u][v] == 1);
} else {
valid &= (p[u][v] == 2);
}
}
}
assert(cc.size() > 0);
valid &= (cc.size() != 2);
if (!valid) return 0;
// Create lines:
for (auto &line: cc) {
rep(i, 1, line.size()) {
int u = line[i - 1], v = line[i];
assert(u != v);
g[u][v] = g[v][u] = 1;
}
}
if (cc.size() >= 3) {
// Merge lines:
rep(i, 0, cc.size()) {
int nxt = (i + 1) % cc.size();
// assert(cc[i].size() >= 1);
// assert(cc[(i + 1) % cc.size()].size() >= 1);
int u = cc[nxt][0], v = cc[i][0];
while (u < 0 || u >= g.size());
while (v < 0 || v >= g.size());
g[u][v] = g[v][u] = 1;
}
}
return 1;
}
int construct(vector<vector<int> > p) {
int n = p.size();
rep(i, 0, n) {
if (p[i][i] != 1) return 0;
// assert(p[i][i] == 1);
}
vvi g(n, vi(n, 0));
vi color(n, -1);
int cur_col = 0;
vvi cc;
rep(i, 0, n) {
if (color[i] >= 0) continue;
color[i] = cur_col++;
cc.push_back({i});
rep(j, i+1, n) {
if (p[i][j] >= 1) {
if (color[j] >= 0) return 0;
color[j] = color[i];
cc.back().push_back(j);
}
}
}
rep(i, 0, n) {
rep(j, 0, n) {
if ((p[i][j] > 0) ^ (color[i] == color[j])) {
return 0;
}
}
}
for (auto &comp: cc) {
if (!handle_comp(p, g, comp)) return 0;
}
build(g);
return 1;
}
/*
1
1
2
1 1
1 1
3
1 1 1
1 1 1
1 1 1
3
1 1 1
1 1 0
1 0 1
3
1 0 1
0 1 0
1 0 1
3
1 2 2
2 1 2
2 2 1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
3
1 2 0
0 1 2
2 0 1
3
1 1 2
2 1 1
2 1 1
5
1 0 2 2 2
0 1 2 2 2
0 2 1 2 2
0 2 2 1 2
0 2 2 2 1
5
1 0 2 1 2
0 1 1 2 2
0 2 1 2 2
0 2 1 1 2
0 2 2 1 1
*/
