#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define pb push_back
#define fi first
#define se second
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
void add ( int &a , int b )
{
a += b ;
if ( a >= mod ) a -= mod ;
if ( a < 0 ) a += mod ;
}
int n , ma , vis [maxn] ;
vi block ,edge , circle ;
vector<vi> graph,res ;
void add_edge ( int u , int v ) { res [u][v] = res [v][u] = 1 ; }
void dfs ( int u )
{
vis [u] = 1 ;
block.pb (u) ;
for ( int v = 0 ; v < n ; v ++ )
{
ma = max (ma,graph[u][v]) ;
if ( !vis [v] && graph [u][v] ) dfs (v) ;
}
}
void dfsCircle ( int u )
{
vis [u] = 2 ;
edge.pb (u) ;
for ( int v = 0 ; v < n ; v ++ ) if ( vis [v] == 1 && graph [u][v] == 1 ) dfsCircle (v) ;
}
int construct( vector<vi> p ) {
graph = p , n = p.size () ; res.resize (n) ;
for ( int i = 0 ; i < n ; i ++ ) res [i].resize (n) ;
for ( int i = 0 ; i < n ; i ++ )
{
if ( vis [i] ) continue ;
ma = 1 ; block.clear() ; dfs (i) ;
if ( ma == 3 ) return 0 ;
int sz = block.size () ;
for ( int j = 1 ; j < sz ; j ++ )
{
for ( int k = 0 ; k < j ; k ++ )
{
if ( !graph[block[j]][block[k]] ) return 0 ;
}
}
if ( ma == 1 ) for ( int j = 1 ; j < sz ; j ++ ) add_edge (block[0],block[j]) ;
else
{
circle.clear() ;
for ( int r = 0 , j = block [r] ; r < sz ; r ++ , j = block [r] )
{
if ( vis [j] != 1 ) continue ;
edge.clear() ;
dfsCircle (j) ;
int sz2 = edge.size() ;
for ( int k = 1 ; k < sz2 ; k ++ )
{
for ( int l = 0 ; l < k ; l ++ )
{
if ( graph[edge[k]][edge[l]] != 1 ) return 0 ;
}
add_edge (edge[0],edge[k]) ;
}
circle.pb(edge[0]) ;
}
if ( circle.size () <= 2 ) return 0 ;
int sz3 = circle.size () ;
for ( int j = 0 ; j < sz3 ; j ++ ) add_edge (circle[j],circle[(j+1)%sz3]) ;
}
}
build (res) ;
return 1;
}
