#include "supertrees.h"
#include <cassert>
#include <map>
#include <vector>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
struct DSU{
vector<int> p;
int n, cnt;
DSU(int N){
n=N;
cnt=n;
p.resize(n, -1);
}
int get(int x){
return p[x]==-1?x:p[x]=get(p[x]);
}
bool unite(int a, int b){
a=get(a);
b=get(b);
if (a==b) return 0;
cnt--;
if (a<b) swap(a, b);
p[a]=b;
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = (int)p.size();
DSU tr(n), tr2(n);
vector<vector<int>> A(n);
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i!=j and p[i][j]){
tr.unite(i, j);
if (p[i][j]==1) tr2.unite(i, j);
}
}
}
map<int, vector<int>> ccs;
for (int i=0; i<n; i++){
// assert(tr.get(i)<tr.cnt);
ccs[tr.get(i)].push_back(i);
}
vector<vector<int>> ans(n, vector<int>(n));
vector<vector<int>> shadow(n, vector<int>(n));
for (auto &[_, arr]:ccs){
map<int, vector<int>> groups;
for (auto ch:arr){
groups[tr2.get(ch)].push_back(ch);
}
vector<int> circle;
for (auto &[icc,mem]:groups){
for (ll j=1; j<(int)mem.size(); j++){
ans[mem[j]][mem[j-1]]=ans[mem[j-1]][mem[j]]=1;
}
for (ll j=0; j<(int)mem.size(); j++){
for (ll k=j+1; k<(int)mem.size(); k++){
shadow[mem[j]][mem[k]]=shadow[mem[k]][mem[j]]=1;
}
}
circle.push_back(mem[0]);
}
if (circle.size()==1) continue;
for (ll j=0; j<(int)circle.size(); j++){
int nxt = (j+1)%(int)(circle.size());
ans[circle[j]][circle[nxt]]=ans[circle[nxt]][circle[j]]=1;
}
for (ll j=0; j<(int)(circle.size()); j++){
for (ll k=j+1; k<(int)(circle.size()); k++){
shadow[circle[j]][circle[k]]=shadow[circle[k]][circle[j]]=2;
}
}
}
for (ll i=0; i<n; i++){
for (ll j=0; j<n; j++){
if ((i!=j and p[i][j]!=shadow[i][j]) or p[i][j]==3){
return 0;
}
}
}
build(ans);
return 1;
}
