#include <iostream>
#include <vector>
#include <algorithm>
#include "supertrees.h"
using namespace std;
const int M = 1005;
vector<int> nei[M];
int seen[M], par[M], Ways[M][M], Dfs[M];
int root(int v){
return (par[v] == -1 ? v : par[v] = root(par[v]));
}
void dfs(int u, int rt){
Dfs[u] = 1;
Ways[rt][u]++;
for (int i : nei[u]){
if (Dfs[i] == 1)
continue;
dfs(i, rt);
}
Dfs[u] = 0;
}
int construct(vector<vector<int>> p){
int n = p.size();
for (int i=0;i<n;i++)
par[i] = -1;
vector<vector<int>> Edge(n, vector<int> (n, 0));
for (int i=0;i<n;i++){
for (int j=i+1;j<n;j++){
if (root(i) != root(j) and p[i][j] == 1){
Edge[i][j] = Edge[j][i] = 1;
par[root(j)] = root(i);
nei[i].push_back(j);
nei[j].push_back(i);
}
}
}
for (int i=0;i<n;i++){
if (seen[root(i)] or i != root(i))
continue;
seen[root(i)] = 1;
int lst = i;
for (int j=0;j<n;j++){
if (p[i][j] == 2 and seen[root(j)] == 0 and j == root(j)){
nei[lst].push_back(j);
nei[j].push_back(lst);
Edge[lst][j] = Edge[j][lst] = 1;
lst = j;
seen[root(j)] = 1;
}
}
if (lst != i){
nei[lst].push_back(i);
nei[i].push_back(lst);
Edge[lst][i] = Edge[i][lst] = 1;
}
}
for (int i=0;i<n;i++)
dfs(i, i);
for (int i=0;i<n;i++){
for (int j=0;j<n;j++)
if (Ways[i][j] != p[i][j])
return 0;
}
build(Edge);
return 1;
}
