#include "supertrees.h"
#include <vector>
#include <set>
using namespace std;
int cpar[1005];
int tpar[1005];
set<int> cv[1005];
int tfind(int x)
{
if (tpar[x] == x)
return x;
return tpar[x] = tfind(tpar[x]);
}
void tmerge(int x, int y)
{
x = tfind(x);
y = tfind(y);
tpar[x] = y;
}
int cfind(int x)
{
if (cpar[x] == x)
return x;
return cpar[x] = cfind(cpar[x]);
}
void cmerge(int x, int y)
{
x = cfind(x);
y = cfind(y);
cpar[x] = y;
}
int construct(vector<vector<int>> p)
{
int n = p.size();
for (int i = 0; i < n; i++)
cpar[i] = tpar[i] = i;
vector<vector<int>> answer;
for (int i = 0; i < n; i++)
{
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i][j] == 0)
continue;
if (p[i][j] == 1)
{
if (tfind(i) == tfind(j))
continue;
tmerge(i, j);
answer[i][j] = answer[j][i] = 1;
continue;
}
if (p[i][j] >= 2)
cmerge(i, j);
}
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i][j] == 0)
{
if (cfind(i) == cfind(j) || tfind(i) == tfind(j))
return 0;
}
if (p[i][j] == 1)
{
if (tfind(i) != tfind(j))
return 0;
}
if (p[i][j] >= 2)
{
if (cfind(i) != cfind(j) || tfind(i) == tfind(j))
return 0;
cv[cfind(i)].insert(p[i][j]);
}
}
}
for (int i = 0; i < n; i++)
{
if (cfind(i) != i)
continue;
set<int> ts;
for (int j = 0; j < n; j++)
{
if (cfind(j) != i)
continue;
ts.insert(tfind(j));
}
vector<int> tv;
for (auto ti : ts)
tv.push_back(ti);
int k = tv.size();
if (k <= 1)
continue;
if (cv[i].size() >= 2 || *cv[i].begin() == 3)
return 0;
if (k <= 2)
return 0;
for (int x = 0; x < k; x++)
{
int nx = (x + 1) % k;
answer[tv[x]][tv[nx]] = answer[tv[nx]][tv[x]] = 1;
}
}
build(answer);
return 1;
}
