#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " <<
using namespace std;
struct DSU {
vi dad;
DSU(int nn) {
dad.resize(nn);
iota(all(dad),0ll);
}
int find(int x) {
if (x == dad[x]) return x;
return dad[x] = find(dad[x]);
}
void unite(int x,int y) {
dad[find(x)] = find(y);
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vi> answer(n,vi(n,0));
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++) {
if (p[i][j] == 3) return 0;
}
}
DSU dsu(n);
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++) {
if (p[i][j]) dsu.unite(i,j);
}
}
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++) {
if ((dsu.find(i) == dsu.find(j)) != !!(p[i][j])) return 0;
}
}
DSU dsu2(n);
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++) {
if (p[i][j] == 1) dsu2.unite(i,j);
}
}
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++) {
if (dsu2.find(i) == dsu2.find(j) && p[i][j] != 1) return 0;
}
}
vi stuf[n];
for (int i = 0;i<n;i++) stuf[dsu2.find(i)].push_back(i);
for (int i = 0;i<n;i++) {
if (stuf[i].empty()) continue;
for (int j = 0;j<stuf[i].size()-1;j++) {
answer[stuf[i][j]][stuf[i][j+1]] = answer[stuf[i][j+1]][stuf[i][j]] = 1;
if (p[stuf[i][j]] != p[stuf[i][j+1]]) return 0;
}
}
vi uc;
for (int i = 0;i<n;i++) if (stuf[i].size()) uc.push_back(stuf[i][0]);
sort(all(uc));
DSU dsu3(n);
for (int i = 0;i<uc.size();i++) {
int a = uc[i];
int have = 0;
for (int j = 0;j<n;j++) {
if (p[a][j] == 2) {
have = 1;
}
}
if (!have) continue;
int found = -1;
for (int j = i+1;j<uc.size();j++) {
int b = uc[j];
if (p[a][b] == 2) {
found = b;
break;
}
}
if (found == -1) {
for (int j = 0;j<i;j++) {
int b = uc[j];
if (p[a][b] == 2) {
found = b;
break;
}
}
if (found == -1) return 0;
}
dsu3.unite(a,found);
answer[a][found] = answer[found][a] = 1;
found = -1;
for (int j = i-1;j>=0;j--) {
int b = uc[j];
if (p[a][b] == 2) {
found = b;
break;
}
}
if (found == -1) {
for (int j = uc.size()-1;j > i;j++) {
int b = uc[j];
if (p[a][b] == 2) {
found = b;
break;
}
}
if (found == -1) return 0;
}
dsu3.unite(a,found);
answer[a][found] = answer[found][a] = 1;
}
for (int i = 0;i<uc.size();i++) {
for (int j = 0;j<uc.size();j++) {
if (i == j) continue;
if ((p[uc[i]][uc[j]] == 2) != (!!(dsu3.find(uc[i]) == dsu3.find(uc[j])))) return 0;
}
}
build(answer);
return 1;
}
