#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 1e3 + 5;
ll n, bisa = 1, p[NN], x[NN];
std::vector<std::vector<int>> answer;
vector<ll> v[NN];
std::vector<std::vector<int>> px;
ll car(ll pos)
{
if(p[pos] == pos)
return pos;
else
return p[pos] = car(p[pos]);
}
int construct(std::vector<std::vector<int>> pt) {
px = pt;
n = px.size();
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n, 0);
answer.push_back(row);
}
for (int i = 0; i < n; i++)
p[i] = i;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if(px[i][j])
p[car(i)] = car(j);
for (int i = 0; i < n; i++)
v[car(i)].pb(i);
for (int i = 0; i < n; i++)
{
if(!bisa)
break;
ll sz = v[i].size();
x[0] = 0;
x[1] = 0;
x[2] = 0;
x[3] = 0;
for(ll j = 0; j < sz; j++)
for(ll k = j + 1; k < sz; k++)
x[px[v[i][j]][v[i][k]]] = 1;
if(x[0] + x[1] + x[2] + x[3] == 0)
continue;
else
if(x[0])
bisa = 0;
else
if(x[2] == 1 && x[3] == 1)
bisa = 0;
else
if(x[1] == 1 && x[2] == 0 && x[3] == 0)
{
for(ll j = 1; j < sz; j++)
{
answer[v[i][j - 1]][v[i][j]] = 1;
answer[v[i][j]][v[i][j - 1]] = 1;
}
}
else
if(x[2] == 1 && x[1] == 0)
{
if(sz <= 2)
bisa = 0;
else
{
for(ll j = 0; j < sz; j++)
{
answer[v[i][j]][v[i][(j + 1) % sz]] = 1;
answer[v[i][(j + 1) % sz]][v[i][j]] = 1;
}
}
}
}
if(!bisa)return 0;
build(answer);
return 1;
}
