#include <iostream>
#include <map>
#include <vector>
#include "supertrees.h"
using namespace std;
const int N = 1<<10;
vector<int> nei[N];
int rt[N], cur, mod = 1e9 + 7;
int num[N][N], vis[N];
map<int, bool> seen[N];
void Add(int i, int j, vector<vector<int>> adj){
nei[i].push_back(j);
nei[j].push_back(i);
adj[i][j] = adj[j][i] = i;
}
void dfs(int u, int h){
h = (1LL * h * 53 * 51 + u) % mod;
if (seen[u][h])
return;
seen[u][h] = 1, num[cur-1][u]++;
vis[u] = cur;
for (int i : nei[u])
if (vis[u] != cur)
dfs(i, h);
}
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> adj(n, vector<int> (n, 0));
for (int i=0;i<n;i++)
rt[i] = -1;
for (int i=0;i<n;i++){
if (rt[i] == -1){
rt[i] = i;
for (int j=0;j<n;j++)
if (i != j and p[i][j] == 1)
rt[j] = i, Add(i, j, adj);
}
}
for (int i=0;i<n;i++){
int t = 1;
for (int j=i+1;t and j<n;j++){
if (i == rt[i] and j == rt[j] and p[i][j] == 2)
Add(i, j, adj), t = 0;
}
for (int j=0;t and j < i;j++){
if (i == rt[i] and j == rt[j] and p[i][j] == 2)
Add(i, j, adj), t = 0;
}
}
for (int i=0;i<n;i++){
++cur;
dfs(i, i);
for (int j=0;j<n;j++)
if (num[i][j] != p[i][j])
return 0;
}
build(adj);
return 1;
}
