#include <iostream>
#include "supertrees.h"
#include <vector>
#include <set>
using namespace std;
const int N = 1002;
vector<vector<int>> p;
vector<vector<int>> answer;
set<int> dsu[N];
vector<int> ds[N];
int com[N];
void dfs(int v) {
for (auto to : dsu[v]) {
if (com[to]) continue;
com[to] = com[v];
dfs(to);
}
}
void connect(int a, int b) {
if (a == b) return;
answer[a][b] = 1;
answer[b][a] = 1;
}
bool solve(vector<int> v) {
int n = v.size();
vector<bool> f(n);
fill(f.begin(), f.end(), true);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[v[i]][v[j]] == 1) {
f[i] = 0;
f[j] = 0;
}
}
}
vector<int> u(n);
int c = 0;
int first = -1, last = -1;
for (int i = 0; i < n; i++) {
if (f[i]) {
u[i] = c;
if (first < 0) {
first = i;
last = i;
}
connect(v[last], v[i]);
last = i;
}
}
for (int i = 0; i < n; i++) {
if (!f[i] && !u[i]) {
u[i] = ++c;
if (first < 0) {
first = i;
last = i;
}
connect(v[last], v[i]);
last = i;
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (p[v[i]][v[j]] == 1) {
connect(v[i], v[j]);
u[j] = c;
}
}
}
}
if (answer[v[last]][v[first]]) return 0;
connect(v[last], v[first]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[v[i]][v[j]] == 1 && u[i] != u[j])
return 0;
if(p[v[i]][v[j]] == 2 && (u[i] && u[i] == u[j]))
return 0;
}
}
return 1;
}
int construct(vector<vector<int>> pp) {
p = pp;
int n = p.size();
answer.resize(n);
for (int i = 0; i < n; i++) {
answer[i].resize(n);
}
bool noBitches = false; //suta
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (p[i][j]) {
dsu[i].insert(j);
ds[i].push_back(j);
}
if (p[i][j] == 3) {
noBitches = true;
}
}
}
if (!noBitches) {
return 0;
}
int k = 1;
for (int i = 0; i < n; i++) {
if (!com[i]) {
com[i] = k++;
dfs(i);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (com[i] == com[j] && dsu[i].find(j) == dsu[i].end()) return 0;
if (com[i] != com[j] && dsu[i].find(j) != dsu[i].end()) return 0;
}
}
for (int i = 0; i < n; i++) {
if (com[i]) {
if (dsu[i].size() == 0) continue;
vector<int> c;
c.push_back(i);
com[i] = 0;
for (int j : dsu[i]) {
c.push_back(j);
com[j] = 0;
}
if (!solve(c))
return 0;
}
}
build(answer);
return 1;
}
/*
3
1 0 0
0 1 1
0 1 1
4
1 0 0 0
0 1 2 2
0 2 1 2
0 2 2 1
3
1 0 0
0 1 2
0 2 1
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
8
1 2 2 2 2 2 0 0
2 1 2 2 2 2 0 0
2 2 1 2 1 2 0 0
2 2 2 1 2 1 0 0
2 2 1 2 1 2 0 0
2 2 2 1 2 1 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
*/
