/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
#include "supertrees.h"
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=1001;
struct my_dsu{
vector<int> vec[MAXN];
int fa[MAXN];
int root(int u){
return fa[u]=(fa[u]==u? u:root(fa[u]));
}
void merge(int u,int v){
u=root(u);
v=root(v);
if(u==v) return;
if(vec[u].size()>vec[v].size()) swap(u,v);
for(auto it:vec[u])
vec[v].PB(it);
fa[u]=v;
vec[u].clear();
}
}dsu,dsu2;
bool three[MAXN];
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
rep(i,n)
dsu.fa[i]=i,dsu.vec[i].PB(i),dsu2.fa[i]=i,dsu2.vec[i].PB(i);
vector<vector<int> > ans=vector<vector<int> > (n,vector<int> (n,0));
rep(i,n)
rep(j,n){
if(p[i][j]==1){
dsu.merge(i,j);
}
}
rep(i,n)
rep(j,n)
if(dsu.root(i)==dsu.root(j)){
if(p[i][j]!=1) return 0;
}
rep(i,n)
if(dsu.root(i)==i)
{
int las=-1;
for(auto it:dsu.vec[i])
{
if(las!=-1){
ans[las][it]=ans[it][las]=1;
}
las=it;
}
}
// rep(i,n)
// if(dsu.root(i)==i){
// for(auto it:dsu.vec[i]) cout<<it<<' ';
// cout<<endl;
// }
rep(i,n)
rep(j,n)
if(p[i][j]>1){
// cout<<dsu.root(i)<<'_'<<dsu.root(j)<<endl;
dsu2.merge(dsu.root(i),dsu.root(j));
}
rep(i,n)
rep(j,n)
if(dsu.root(i)!=dsu.root(j))
if(dsu2.root(dsu.root(i))==dsu2.root(dsu.root(j))){
if(p[i][j]<=1){
// cout<<'!'<<' '<<i<<" "<<j<<endl;
return false;
}
}
rep(i,n)
if(dsu2.root(i)==i){
if(dsu2.vec[i].size()==1) continue;
if(dsu2.vec[i].size()==2) return 0;
int las=dsu2.vec[i].back();
for(auto it:dsu2.vec[i]){
ans[it][las]=ans[las][it]=1;
las=it;
}
}
// cout<<"TONOW\n";
rep(i,n)
rep(j,n)
if(p[i][j]==3){
three[dsu2.root(dsu.root(i))]=1;
}
rep(i,n)
if(three[i]){
if(dsu2.vec[i].size()<=3) return 0;
ans[dsu2.vec[i][0]][dsu2.vec[i][2]]=ans[dsu2.vec[i][2]][dsu2.vec[i][0]]=1;
}
rep(i,n)
rep(j,n)
if(dsu2.root(dsu.root(i))==dsu2.root(dsu.root(j))){
if(three[dsu2.root(dsu.root(i))]){
if(p[i][j]!=3) return false;
}
}
// for(auto it:ans){
// for(auto itt:it){
// cout<<itt<<' ';
// }
// cout<<endl;
// }
build(ans);
return 1;
}
//int main(){
// fastio;
// cout<<construct({{1,3},{3,1}});
// return 0;
//}
