#include "supertrees.h"
#include <vector>
using namespace std;
int papa[1010];
vector<int> fii[1010];
int realPapa(int x)
{
return x == papa[x] ? x : papa[x] = realPapa(papa[x]);
}
void join(int x, int y)
{
papa[realPapa(x)] = realPapa(y);
}
int construct(vector<vector<int>> p)
{
int n = p.size();
vector<vector<int>> ret(n, vector<int>(n));
for(int i = 0; i < n; i ++)
papa[i] = i;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(p[i][j] == 3)
return 0;
if(p[i][j])
join(i, j);
}
}
for(int i = 0; i < n; i ++)
fii[realPapa(i)].push_back(i);
for(int i = 0; i < n; i ++)
if(fii[i].size())
{
vector<int> tmp = fii[i];
for(int j : tmp)
for(int k : tmp)
if(p[j][k] == 0)
return 0;
for(int j : tmp)
papa[j] = j, fii[j].clear();
for(int j : tmp)
for(int k : tmp)
if(p[j][k] == 1) join(j, k);
for(int j : tmp)
fii[realPapa(j)].push_back(j);
vector<int> head;
for(int j : tmp)
if(fii[j].size())
{
head.push_back(j);
for(int k : fii[j])
for(int l : fii[j])
if(p[k][l] == 2)
return 0;
for(int k = 0; k < (int)fii[j].size() - 1; k ++)
ret[fii[j][k]][fii[j][k + 1]] = ret[fii[j][k + 1]][fii[j][k]] = 1;
}
if(head.size() == 2)
return 0;
if(head.size() >= 3)
{
for(int j = 0; j < (int)head.size() - 1; j ++)
ret[head[j]][head[j + 1]] = ret[head[j + 1]][head[j]] = 1;
ret[head.back()][head[0]] = ret[head[0]][head.back()] = 1;
}
}
build(ret);
return 1;
}
