#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU
{
int n = -37;
vector<int> par;
DSU(int sz) : n(sz) {
par.assign(n, -1);
}
int get(int x) {
return (par[x] < 0 ? x : par[x] = get(par[x]));
}
bool merge(int x, int y) {
x = get(x);
y = get(y);
if(x == y) {
return false;
}
assert(par[x] < 0 and par[y] < 0);
if(par[x] > par[y]) {
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
DSU single(n);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < i; ++j) {
if(p[i][j] == 1) {
single.merge(i, j);
}
}
}
// cout << "Single\n---------\n";
// for(int i = 0; i < n; ++i) {
// cout << i << " : " << single.get(i) << endl;
// }
DSU cycles = single;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < i; ++j) {
if(p[i][j] == 2) {
if(single.get(i) == single.get(j)) {
return 0;
}
cycles.merge(i, j);
}
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < i; ++j) {
if(p[i][j] == 0) {
if(single.get(i) == single.get(j) or cycles.get(i) == cycles.get(j)) {
return 0;
}
}
}
}
vector<vector<int> > lines(n), answer(n, vector<int>(n)), circles(n);
for(int i = 0; i < n; ++i) {
lines[single.get(i)].push_back(i);
}
for(int i = 0; i < n; ++i) {
const int sz = lines[i].size();
// cout << "Line : ";
// for(int x : lines[i]) {
// cout << x << ' ';
// }cout << endl;
for(int j = 1; j < sz; ++j) {
int prev = lines[i][j - 1], cur = lines[i][j];
answer[prev][cur] = answer[cur][prev] = 1;
}
}
for(int i = 0; i < n; ++i) {
if(single.get(i) != i) {
continue;
}
circles[cycles.get(i)].push_back(i);
}
// cout << "Cycle\n------------\n";
// for(int i = 0; i < n; ++i) {
// cout << i << " : " << cycles.get(i) << endl;
// }
for(int i = 0; i < n; ++i) {
if(circles[i].size() < 2u) {
continue;
}
if(circles[i].size() == 2u) {
return 0;
}
const int sz = circles[i].size();
for(int j = 0; j < sz; ++j) {
int cur = circles[i][j], to = circles[i][(j + 1) % sz];
assert(answer[cur][to] == answer[to][cur] and answer[cur][to] == 0);
answer[cur][to] = answer[to][cur] = 1;
}
}
build(answer);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
2
1 0
0 1
2
1 2
2 1
*/
