#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 fromset[maxn];
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])
{
if(p[i][j] == 3)return 0;
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);
memset(fromset, -1, sizeof(fromset));
vector < int > lead;
for (int j = 0; j < path.size(); ++ j)
{
int x = path[j];
if(fromset[j] != -1)continue;
fromset[j] = x;
int pre = x;
lead.pb(x);
for (int jj = j+1; jj < path.size(); ++ jj)
{
if(fromset[jj] != -1)continue;
int y = path[jj];
if(p[x][y] == 1)
{
fromset[jj] = x;
answer[y][pre] = 1;
answer[pre][y] = 1;
pre = y;
}
}
}
if(lead.size() >= 3)
{
int lastv = lead.back();
for (auto v: lead)
{
answer[lastv][v] = 1;
answer[v][lastv] = 1;
lastv = v;
}
}
else if(lead.size() == 2)return 0;
/*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;
}
