#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x; return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<int> cycle[n+1];
vector<vector<int>> ans(n, vector<int> (n));
DSU dsu = DSU(n);
for(int i = 0;i<n;i++) {
for(int j = 0;j<n;j++) {
if(p[i][j] == 3 or p[i][j]!=p[j][i])return 0;
if(p[i][j]==1)dsu.unite(i,j);
}
}
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
if(p[i][j]!=p[i][dsu.get(j)] and p[i][j]!=p[dsu.get(i)][j] and p[i][j]!=p[dsu.get(i)][dsu.get(j)])return 0;
vector<int> trees;
for(int i = 0;i<n;i++) {
int c = dsu.get(i);
if(c == i)
trees.push_back(i);
else ans[i][c]=ans[c][i]=1;
}
dsu = DSU(n);
for(int i:trees) {
for(int j:trees) {
if(p[i][j]==2)dsu.unite(i,j);
}
if(dsu.size(i)-1) {
cycle[dsu.get(i)].push_back(i);
}
}
for(int i = 0;i < n;i++) {
if(!cycle[i].size())continue;
if((int)cycle[i].size()<=2)return 0;
for(int j:cycle[i]) {
for(int k:cycle[i]) {
if(j==k)continue;
if(p[j][k]!=2)return 0;
}
}
for(int j = 0;j<(int)cycle[i].size()-1;j++) {
ans[cycle[i][j]][cycle[i][j+1]]=1;
ans[cycle[i][j+1]][cycle[i][j]]=1;
}
ans[cycle[i][0]][cycle[i].back()]=1;
ans[cycle[i].back()][cycle[i][0]]=1;
}
build(ans);
return 1;
}
