#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(int)(n);i++)
using namespace std;
struct UnionFind{
vector<int>par;
UnionFind(int n){
par=vector<int>(n);
rep(i,n)par[i]=i;
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);y=find(y);
par[y]=x;
}
bool same(int x,int y){
return find(x)==find(y);
}
};
static vector<int>v[2000],v2[2000];
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
UnionFind uf1(n);
rep(i,n)rep(j,n){
if(p[i][j]==1)uf1.unite(i,j);
}
rep(i,n){
v[uf1.find(i)].push_back(i);
}
UnionFind uf2(n);
rep(i,n)for(int j=i+1;j<n;j++){
if(!v[i].empty()&&!v[j].empty()&&p[i][j]==2){
uf2.unite(i,j);
}
}
rep(i,n){
if(!v[i].empty())v2[uf2.find(i)].push_back(i);
}
rep(i,n){
if(v2[i].size()>1){
if(v2[i].size()==2)return 0;
rep(j,v2[i].size()){
answer[v2[i][j]][v2[i][(j+1)%v2[i].size()]]=1;
answer[v2[i][(j+1)%v2[i].size()]][v2[i][j]]=1;
}
}
}
rep(i,n){
if(v[i].size()>1){
rep(j,v[i].size()-1){
answer[v[i][j]][v[i][j+1]]=1;
answer[v[i][j+1]][v[i][j]]=1;
}
}
}
build(answer);
return 1;
}
