#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ve vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
int par1[1001], par2[1001], check[1001], check2[1001];
ve<int> nodes[1001];
int root(int u, int* par) {
if (u == par[u]) return u;
return par[u] = root(par[u], par);
}
void join(int u, int v, int* par) {
u = root(u, par); v = root(v, par);
if (u != v) par[u] = v;
}
int construct(ve<ve<int>> p) {
int n = p.size();
ve<ve<int>> answer;
for (int i = 0; i < n; i++) {
ve<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i=0; i<n; i++) {
par1[i] = i;
par2[i] = i;
}
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (p[i][j] == 1) {
if (root(i, par1) != root(j, par1)) {
join(i, j, par1);
answer[i][j] = 1;
answer[j][i] = 1;
}
}
else if (p[i][j] == 2) {
join(i, j, par2);
}
}
}
for (int i=0; i<n; i++) {
if (!check[root(i, par1)]) {
check[root(i, par1)] = 1;
nodes[root(i, par2)].pb(i);
}
}
for (int i=0; i<n; i++) {
int u = root(i, par2);
if (!check2[u] && nodes[u].size() > 2) {
check2[u] = 1;
for (int j=0; j<nodes[u].size()-1; j++) {
answer[nodes[u][j]][nodes[u][j+1]] = 1;
answer[nodes[u][j+1]][nodes[u][j]] = 1;
}
answer[nodes[u][0]][nodes[u][nodes[u].size()-1]] = 1;
answer[nodes[u][nodes[u].size()-1]][nodes[u][0]] = 1;
}
}
build(answer);
return 1;
}
