#include <bits/stdc++.h>
#include "supertrees.h"
#define mp make_pair
#define X first
#define Y second
#define taskname " "
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int N = 1000;
const int base = 7;
struct _dsu{
int root[N], rnk[N];
void init(int n){
for(int i = 0; i < n; i++){
root[i] = i;
rnk[i] = 0;
}
}
int getRoot(int u){
if (u == root[u])
return u;
root[u] = getRoot(root[u]);
return root[u];
}
bool unite(int u, int v){
u = getRoot(u);
v = getRoot(v);
if (u == v)
return 0;
if (rnk[u] < rnk[v])
swap(u, v);
root[v] = u;
rnk[u] += (rnk[u] == rnk[v]);
return 1;
}
bool check(int u, int v){
return (getRoot(u) == getRoot(v));
}
} dsu;
ll hashing(const vector<int> &a){
ll res = 0;
for(int x : a)
res = res * base + x;
return res;
}
int construct(vector<vector<int>> _a){
int n = _a.size();
vector<vector<int>> res(n, vector<int>(n, 0));
vector<ll> hashed(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if (_a[i][j] == 3)
return 0;
for(int i = 0; i < n; i++)
hashed[i] = hashing(_a[i]);
dsu.init(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if (_a[i][j] == 1 && i != j){
if (dsu.unite(i, j)){
res[i][j] = res[j][i] = 1;
}
if (hashed[i] != hashed[j])
return 0;
}
vector <int> roots;
for(int i = 0; i < n; i++)
if (dsu.getRoot(i) == i){
int cur = i;
int cnt = 0;
for(int j = 0; j < n; j++)
if (_a[i][j] == 2 && dsu.getRoot(j) == j){
cnt++;
dsu.unite(i, j);
res[cur][j] = res[j][cur] = 1;
cur = j;
}
if (cur != i && cnt < 2)
return 0;
if (cur != i)
res[i][cur] = res[cur][i] = 1;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if ((_a[i][j] > 0) != dsu.check(i, j))
return 0;
build(res);
return 1;
}
