#include "supertrees.h"
//#include <vector>
#define vi vector<int>
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1005;
int par[MAXN];
int twos[MAXN];
vector<vector<int> > elems(MAXN);
auto cmp = [](int a, int b)
{
//cout << a << " " << b << "\n";
if(twos[a] != twos[b])
return twos[a] > twos[b];
else
return a > b;
};
int findset(int a)
{
if(par[a] == a)
return a;
return par[a] = findset(par[a]);
}
int mergeset(int a, int b)
{
a = findset(a), b = findset(b);
if(a == b)
return 0;
//if(a > b)
//swap(a,b);
par[b] = a;
return a;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
for(int i = 0; i < n; i++)
par[i] = i;
for(int i = 0; i < n; i++)
{
if(findset(i) == i) // New component
{
elems[i].push_back(i);
for(int a = 0; a < n; a++)
{
if(i == a || p[i][a] == 0)
continue;
//cout << i << " " << a << "\n";
if(findset(a) == a)
{
mergeset(i, a);
elems[i].push_back(a);
}
}
}
}
bool valid = true;
for(int i = 0; i < n; i++)
{
vi incycle;
if(elems[i].size() == 0)
continue;
set<int, decltype(cmp)> curr(cmp);
for(int a : elems[i])
{
for(int l = 0; l < n; l++)
{
if(p[a][l] == 2)
twos[a]++;
}
//cout << a << ""
curr.insert(a);
}
int lastelem = -1;
//for(int e : curr)
//cout << "Hm: " << e << "\n";
while(!curr.empty())
{
int v = *(curr.begin());
//cout << v << "\n";
curr.erase(curr.begin());
if(incycle.size() > 0)
{
lastelem = incycle.back();
//cout << v << " " << lastelem
answer[v][lastelem] = answer[lastelem][v] = 1;
}
incycle.push_back(v);
//cout << v << " " << curr.size() << "\n";
vi torem;
for(int a : curr)
{
//cout << v << " " << a << " " << p[a][v] << "\n";
if(p[v][a] == 1) {
//cout << v << " " << a << "\n";
answer[v][a] = answer[a][v] = 1;
torem.push_back(a);
//curr.erase(a);
}
}
for(int e : torem)
curr.erase(e);
}
if(incycle.size() > 1)
answer[incycle.back()][incycle[0]] = answer[incycle[0]][incycle.back()] = 1;
else if(incycle.size() == 1)
valid = false;
}
//if(incycle[i] != )
if(valid) {
build(answer);
return 1;
}
else
return 0;
}
