#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct DSU{
ll N;
vector<ll> par, sz;
DSU(ll _n){
N = _n;
par.resize(N + 5), sz.resize(N + 5);
iota(par.begin(), par.end(), 0LL);
for(int i = 0; i < N; i++) sz[i] = 1;
}
ll find(ll idx){
return par[idx] == idx ? idx : par[idx] = find(par[idx]);
}
void join(ll a, ll b){
a = find(a), b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
// check ada 3 ato ga
bool ok = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
ok &= (p[i][j] != 3);
}
}
if(!ok) return 0;
DSU dsu1(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 1) dsu1.join(i, j);
}
}
DSU dsu2(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 2) dsu2.join(dsu1.find(i), dsu1.find(j));
}
}
// check connectivity
for(int i = 0; i < n; i++){
ok &= (dsu2.sz[dsu2.find(i)] != 2);
for(int j = 0; j < n; j++){
if(dsu2.find(dsu1.find(j)) == dsu2.find(dsu1.find(i))){
if(dsu1.find(i) == dsu1.find(j)) ok &= (p[i][j] == 1);
else ok &= (p[i][j] == 2);
}
else{
ok &= (p[i][j] == 0);
}
}
}
if(!ok) return 0;
for(int i = 0; i < n; i++){
if(dsu2.find(i) != i) continue;
vector<ll> v;
for(int j = 0; j < n; j++){
if(dsu2.find(j) == i) v.push_back(j);
}
for(int j = 0; j < (int)v.size() - 1; j++){
answer[v[j]][v[j + 1]] = answer[v[j + 1]][v[j]] = 1;
}
if(v.size() > 1){
answer[v[0]][v.back()] = answer[v.back()][v[0]] = 1;
}
}
for(int i = 0; i < n; i++){
if(dsu1.find(i) != i) continue;
vector<ll> v;
for(int j = 0; j < n; j++){
if(dsu1.find(j) == i && i != j) v.push_back(j);
}
for(int j = 0; j < (int)v.size(); j++){
answer[v[j]][i] = answer[i][v[j]] = 1;
}
}
build(answer);
return 1;
}
