#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1005;
vector<int> g[mxn];
vector<int> comp;
bool vis[mxn];
struct DSU{
int sz[mxn];
int g[mxn];
DSU(int n){
for(int i = 0 ;i<n;i++){
sz[i] = 1;
g[i] = i;
}
}
int find(int x){
if(x == g[x])return x;
return g[x] = find(g[x]);
}
bool unite(int a,int b){
a = find(a);
b = find(b);
if(a == b)return false;
if(sz[a] > sz[b])swap(a,b);
g[a] = b;
sz[b] += sz[a];
return true;
}
inline bool same(int a,int b){
return find(a) == find(b);
}
};
void dfs(int x){
vis[x] = true;
comp.push_back(x);
for(auto y : g[x]){
if(vis[y])continue;
dfs(y);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
DSU d(n);
vector<vector<int> > ans(n,vector<int>(n,0));
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
//ans[i][j] = ans[j][i] = 0;
if(p[i][j] == 3)return 0;
if(p[i][j] == 1)d.unite(i,j);
}
}
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(d.same(i,j) && p[i][j] == 0)return 0;
}
}
for(int i = 0;i<n;i++){
if(d.find(i) != i){
ans[i][d.find(i)] = ans[d.find(i)][i] = 1;
}
}
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(p[i][j] == 2 && d.find(i) == i && d.find(j) == j){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for(int i = 0;i<n;i++){
if(vis[i] || d.find(i) != i)continue;
comp.clear();
dfs(i);
if(comp.size() == 2)return 0;
for(auto x : comp){
for(auto y : comp){
if(x != y && p[x][y] != 2)return 0;
}
}
int sz = comp.size();
for(int j = 0;j<sz-1;j++){
ans[comp[j]][comp[j+1]] = ans[comp[j+1]][comp[j]] = 1;
}
if(sz != 1)ans[comp[0]][comp.back()] = ans[comp.back()][comp[0]] = 1;
}
build(ans);
return 1;
}
