#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int parent[1001];
int find(int x) {
if(parent[x]<0) return x;
return parent[x]=find(parent[x]);
}
void merge(int x, int y) {
x=find(x), y=find(y);
if(x==y) return;
if(parent[x]>parent[y]) swap(x, y);
parent[x]+=parent[y];
parent[y]=x;
}
vector<int> adj[1001], cc[1001], root;
vector<vector<int>> ans;
bool visited[1001];
int construct(vector<vector<int>> p) {
int n = p.size();
ans.resize(n);
for(int i=0; i<n; i++) {
ans[i].resize(n);
for(int j=0; j<n; j++) ans[i][j]=0;
}
for(int i=0; i<n; i++) {
if(p[i][i]!=1) return 0;
for(int j=0; j<n; j++) if(p[i][j]!=p[j][i] || p[i][j]==3) return 0;
}
memset(parent, -1, sizeof(parent));
for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(p[i][j]) merge(i, j);
for(int i=0; i<n; i++) root.push_back(find(i));
sort(root.begin(), root.end());
root.erase(unique(root.begin(), root.end()), root.end());
vector<int> v;
for(int i=0; i<(int)root.size(); i++) {
for(int j=0; j<n; j++) if(find(j)==root[i]) cc[i].push_back(j);
for(auto j: cc[i]) {
for(auto k: cc[i]) if(j!=k) {
if(!p[j][k]) return 0;
if(p[j][k]==1) adj[j].push_back(k);
}
if(!visited[j]) {
v.push_back(j);
for(auto k: adj[j]) visited[k]=1;
}
}
if(v.size()==2) return 0;
for(auto j: v) for(auto k: v) if(j<k) {
for(auto l: adj[j]) for(auto m: adj[k]) if(l==m || p[l][m]==1) return 0;
}
for(auto j: v) for(auto l: adj[j]) for(auto k: adj[j]) if(p[k][l]==2) return 0;
for(auto j: v) for(auto k: adj[j]) ans[j][k]=ans[k][j]=1;
if(v.size()>2) for(int j=0; j<(int)v.size(); j++) {
int a=v[j], b=(j?v[j-1]:v.back());
ans[a][b]=ans[b][a]=1;
}
v.clear();
memset(visited, 0, sizeof(visited));
}
build(ans);
return 1;
}
