#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
#define pb push_back
using namespace std;
const int maxn = 1e3 + 10;
vector < int > initg[maxn];
int initc[maxn], currc;
vector < int > path;
void dfs(int beg)
{
path.pb(beg);
initc[beg] = currc;
for (auto nb: initg[beg])
if(!initc[nb])dfs(nb);
}
int construct(std::vector<std::vector<int>> p)
{
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; ++ i)
{
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector < pair < int, int > > initp;
int okval = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; ++ j)
{
if(i == j)continue;
if(p[i][j])
{
okval = p[i][j];
initg[i].pb(j);
initg[j].pb(i);
}
else initp.pb(make_pair(i, j));
}
}
for (int i = 0; i < n; ++ i)
{
if(initc[i])continue;
path.clear();
currc ++;
dfs(i);
if(okval == 1)
{
int lastv = -1;
for (auto v: path)
{
if(lastv == -1)
{
lastv = v;
continue;
}
answer[lastv][v] = 1;
answer[v][lastv] = 1;
lastv = v;
}
}
else
{
if(path.size() == 1)continue;
if(path.size() == 2)return 0;
int lastv = path.back();
for (auto v: path)
{
answer[lastv][v] = 1;
answer[v][lastv] = 1;
lastv = v;
}
}
}
for (auto &[x, y]: initp)
if(initc[x] == initc[y])return 0;
build(answer);
return 1;
}
