#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
const int N = 1002;
int p[N], sz[N], e[N];
int p1[N][N], sz1[N][N], e1[N][N];
int fs(int x){
if(p[x] == x) return x;
else return p[x] = fs(p[x]);
}
void merge(int a, int b){
a = fs(a), b = fs(b);
if(a == b){
e[a]++;
return;
}
if(sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
e[a] += e[b] + 1;
}
int fs1(int c, int x){
if(p1[c][x] == x) return x;
else return p1[c][x] = fs1(c, p1[c][x]);
}
void merge1(int c, int a, int b){
a = fs1(c,a), b = fs1(c,b);
if(sz1[c][a] == 0) sz1[c][a]++;
if(sz1[c][b] == 0) sz1[c][b]++;
if(a == b){
e1[c][a]++;
return;
}
if(sz1[c][a] < sz1[c][b]) swap(a,b);
p1[c][b] = a;
sz1[c][a] += sz1[c][b];
e1[c][a] += e1[c][b] + 1;
}
int construct(vector<vector<int>> paths) {
int n = paths.size();
for(int i=0; i<n; i++) p[i] = i, sz[i] = 1;
for(int c=0; c<n; c++){
for(int i=0; i<n; i++) p1[c][i] = i;
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(paths[i][j] == 3) return 0;
if(paths[i][j] != 0) merge(i,j);
}
}
bool f = 0;
for(int i=0; i<n; i++){
int c = fs(i);
if(sz[c]*sz[c] != e[c]){
f = 1;
break;
}
}
if(f) return 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int c = fs(i);
if(paths[i][j] == 1) merge1(c,i,j);
}
}
for(int i=0; i<n; i++){
int c = fs(i);
for(int j=0; j<n; j++){
int d = fs1(c,j);
if(sz1[c][d]*sz1[c][d] != e1[c][d]){
f = 1;
break;
}
}
}
if(f) return 0;
vector<vector<int>> ans(n, vector<int>(n));
int done[n] = {};
for(int i=0; i<n; i++){
int c = fs(i);
if(done[c]) continue;
done[c] = 1;
map<int,vector<int>>v;
for(int j=0; j<n; j++){
int d = fs1(c,j);
if(sz1[c][d] == 0) continue;
if(v.find(d) == v.end()) v[d] = vector<int>();
v[d].pb(j);
}
vector<int>temp;
for(auto it = v.begin(); it != v.end(); it++){
auto[id,vec] = *it;
temp.pb(vec[0]);
for(int j=0; j<vec.size()-1; j++){
ans[vec[j]][vec[j+1]] = 1;
ans[vec[j+1]][vec[j]] = 1;
}
}
if(temp.size() > 1) temp.pb(temp[0]);
for(int j=0; j<temp.size()-1; j++){
ans[temp[j]][temp[j+1]] = 1;
ans[temp[j+1]][temp[j]] = 1;
}
}
build(ans);
return 1;
}
