#include "supertrees.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;
const int MAXN = 1e3 + 5;
int N, par[MAXN], branch[MAXN];
int look(int node)
{
if(par[node] == node)
return node;
return par[node] = look(par[node]);
}
void join(int a, int b)
{
par[look(b)] = look(a);
}
int construct(vector<vi> p)
{
N = p.size();
vi branches, cycles;
for(int i = 0; i < N; i++)
{
int one = 0, two = 0;
for(int j = 0; j < N; j++)
{
if(i == j) continue;
if(p[i][j] == 3)
return 0;
if(p[i][j])
join(i, j);
if(p[i][j] == 1)
one = 1;
if(p[i][j] == 2)
two = 1;
}
//part of a branch
if(one)
{
branches.pb(i);
branch[i] = 1;
}
//part of the cycle
else if(two)
cycles.pb(i);
}
vector<vi> answer(N, vi(N, 0));
for(int i = 0; i < N; i++)
par[i] = i;
for(auto i : branch)
{
if(look(i) != i)
continue;
int last = i;
for(int j = 0; j < N; j++)
{
if(i == j) continue;
if(p[i][j] == 1)
{
join(i, j);
answer[last][j] = 1;
answer[j][last] = 1;
last = j;
}
}
cycles.pb(i);
branch[i] = 0;
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j && !p[i][j] && look(i) == look(j))
return 0;
for(int i = 0; i < N; i++)
par[i] = i;
for(auto i : cycles)
{
if(look(i) != i)
continue;
int last = i;
for(int j = 0; j < N; j++)
{
if(i == j) continue;
if(p[i][j] == 2 && !branch[j])
{
join(i, j);
answer[last][j] = 1;
answer[j][last] = 1;
last = j;
}
}
if(last != i)
{
answer[last][i] = 1;
answer[i][last] = 1;
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j && !p[i][j] && look(i) == look(j))
return 0;
build(answer);
return 1;
}
