#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define pb push_back
class DSU {
public:
vt<int>p, size;
void init(int n){
p.resize(n);
size.resize(n);
for (int i=0;i<n;i++){
p[i] = i;
size[i] = 1;
}
}
int get(int a){
return p[a] = (p[a] == a ? a : get(p[a]));
}
void unite(int a, int b){
a = get(a);
b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a,b);
size[b] += size[a];
p[a] = b;
}
};
int construct(vt<vt<int>> p){
int n = sz(p);
vt<vt<int>> b(n, vt<int>(n));
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
b[i][j] = 0;
}
}
DSU cc, one, two;
cc.init(n);
one.init(n);
two.init(n);
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (p[i][j] != 0) cc.unite(i,j);
if (p[i][j] == 1) one.unite(i,j);
if (p[i][j] == 2) two.unite(i,j);
}
}
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (p[i][j] == 0 && cc.get(i) == cc.get(j)) return 0;
}
}
map<int,vt<int>> ones;
for (int i=0;i<n;i++){
ones[one.get(i)].pb(i);
}
vt<bool> processed(n, false);
for (auto &[x,v]: ones){
if (v.size() == 1 && processed[v[0]]) continue;
sort(all(v)); v.erase(unique(all(v)), v.end());
for (int i=0;i<v.size()-1;i++){
b[v[i]][v[i+1]] = 1;
b[v[i+1]][v[i]] = 1;
processed[v[i]]=1;
processed[v[i+1]]=1;
}
//cout << "v = : ";
//for (auto x: v){
// cout << x << " ";
//} cout << endl;
int tail = v.back();
//cout << "tail = " << tail << endl;
vt<int> twos;
for (auto x: v){
for (int y=0;y<n;y++){
if (p[x][y] == 2) twos.pb(y);
}
}
sort(all(twos)); twos.erase(unique(all(twos)), twos.end());
// cout << "twos = : ";
//for (auto x: twos){
// cout << x << " ";
//} cout << endl;
if (twos.size()+1==2) return false;
if (twos.size()>0){
b[tail][twos[0]]=1;
b[twos[0]][tail]=1;
for (int i=0;i<twos.size()-1;i++){
b[twos[i]][twos[i+1]] = 1;
b[twos[i+1]][twos[i]] = 1;
processed[twos[i]]=1;
processed[twos[i+1]]=1;
}
b[tail][twos.back()]=1;
b[twos.back()][tail]=1;
}
}
build(b);
return 1;
}
/*
7
2 2 2 0 0 0 0
2 2 2 0 0 0 0
2 2 2 0 0 0 0
0 0 0 2 0 2 2
0 0 0 0 2 0 0
0 0 0 2 0 2 2
0 0 0 2 0 2 2
*/
/*
9
1 1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
0 0 1 1 2 2 0 0 0
0 0 1 1 2 2 0 0 0
0 0 2 2 1 2 0 0 0
0 0 2 2 2 1 0 0 0
0 0 0 0 0 0 1 2 2
0 0 0 0 0 0 2 1 2
0 0 0 0 0 0 2 2 1
*/
