#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], kel[NN], ket[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)
{
ll te = 0;
for(ll j = 0; j < sz; j++)
{
if(kel[v[i][j]])
continue;
te++;
kel[v[i][j]] = te;
ket[te] = v[i][j];
// cout << te << " " << ket[te] << "_\n"
for(ll k = 0; k < sz; k++)
{
if(j == k)
continue;
if(px[v[i][j]][v[i][k]] == 1)
{
kel[v[i][k]] = te;
// cout << v[i][j] << " " << v[i][k] << "_\n";
answer[v[i][j]][v[i][k]] = 1;
answer[v[i][k]][v[i][j]] = 1;
}
}
}
for(ll j = 0; j < sz; j++)
for(ll k = j + 1; k < sz; k++)
{
if(px[v[i][j]][v[i][k]] == 1 && kel[v[i][j]] != kel[v[i][k]])
bisa = 0;
if(px[v[i][j]][v[i][k]] != 1 && kel[v[i][j]] == kel[v[i][k]])
bisa = 0;
}
if(te <= 2)
bisa = 0;
if(!bisa)
break;
for(ll j = 1; j < te; j++)
{
// cout << ket[j] << " " << ket[j + 1] << "_\n";
answer[ket[j]][ket[j + 1]] = 1;
answer[ket[j + 1]][ket[j]] = 1;
}
answer[ket[te]][ket[1]] = 1;
answer[ket[1]][ket[te]] = 1;
}
else
if(x[3] == 1)
{
bisa = 0;
}
}
if(!bisa)return 0;
build(answer);
return 1;
}
