#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=1010;
int N, A[Nmax][Nmax];
int G[Nmax], cnt, P[Nmax], dist[Nmax];
bool ans[Nmax][Nmax], chk[Nmax];
vector<int> nodes, V[Nmax], adj[Nmax], adj2[Nmax];
int Find(int x) {return G[x]?G[x]=Find(G[x]):x;}
void Union(int x, int y) {
x=Find(x), y=Find(y);
if(x==y) return;
G[x]=y;
}
void DFS(int curr) {
nodes.push_back(curr);
for(int next:adj[curr]) if(!P[next]) {
ans[curr][next]=ans[next][curr]=1;
P[next]=cnt;
DFS(next);
}
}
void DFS2(int curr) {
for(int next:adj[curr]) if(!chk[next]) {
chk[next]=1;
dist[next]++;
DFS2(next);
chk[next]=0;
}
}
int construct(vector<vector<int>> p) {
N=p.size();
for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
A[i][j]=p[i-1][j-1];
if(A[i][j]==3) {cerr<<0; return 0;}
}
for(int i=1; i<=N; i++) {
for(int j=1; j<i; j++) if(A[i][j]) Union(i, j);
}
for(int i=1; i<=N; i++) {
for(int j=1; j<i; j++) if(!A[i][j] && Find(i)==Find(j)) return 0;
}
for(int i=1; i<=N; i++) V[Find(i)].push_back(i);
for(int i=1; i<=N; i++) {
if(V[i].empty()) continue;
for(int j:V[i]) for(int k:V[i]) if(j!=k && A[j][k]==1) {
adj[j].push_back(k);
}
vector<int> tmp;
for(int j:V[i]) if(!P[j]) {
nodes.clear();
P[j]=++cnt;
DFS(j);
for(int k:nodes) for(int l:nodes) if(A[k][l]==2) return 0;
tmp.push_back(j);
}
if(tmp.size()==2) return 0;
for(int j=0; j<(int)tmp.size()-1; j++) ans[tmp[j]][tmp[j+1]]=ans[tmp[j+1]][tmp[j]]=1;
if(tmp.size()>1) ans[tmp.back()][tmp[0]]=ans[tmp[0]][tmp.back()]=1;
}
vector<vector<int>> tmp;
tmp.resize(N);
for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) tmp[i-1].push_back(ans[i][j]);
build(tmp);
return 1;
}
