#include "supertrees.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef pair<int, int> pii;
int construct(vector<vector<int>> A) {
int N = A.size();
for(int i = N; i--;) for(int j = N; j--;)
if(2 < A[i][j]) return 0;
vector<int> B(N, -1);
for(int i = 0; i < N; i++) if(B[i] < 0) {
for(int j = i; j < N; j++) if(1 == A[i][j]) B[j] = i;
}
vector<vector<int>> Cy, Co;
vector<bool> chk(N, false);
for(int i = 0; i < N; i++) if(!chk[i]) {
vector<int> V, U; V.eb(B[i]);
for(int j = 0; j < N; j++) if(A[i][j]) {
U.eb(j);
if(1 == A[i][j]) {
if(chk[j]) return 0;
chk[j] = true;
} else {
if(chk[j]) return 0;
chk[j] = true;
V.eb(B[j]);
}
}
sort(allv(V)); univ(V);
if(2 == sz(V)) return 0;
Cy.eb(V); Co.eb(U);
}
vector<vector<int>> D(N, vector<int>(N, 0));
vector<pii> EV;
for(int ci = 0, cn = sz(Cy); ci < cn; ci++) {
auto &cycle = Cy[ci], &comp = Co[ci];
for(int a : comp) for(int b : comp) D[a][b] = 2;
for(int r : cycle) {
vector<int> V;
for(int v : comp) if(r == B[v]) V.eb(v);
for(int v : V) EV.eb(r, v);
for(int a : V) for(int b : V) D[a][b] = 1;
}
int L = sz(cycle);
if(1 < L) {
for(int i = 0, j = 1; i < L; i++, j++) {
if(j == L) j = 0;
EV.eb(cycle[i], cycle[j]);
}
}
}
for(int i = 0; i < N; i++) if(D[i] != A[i]) return 0;
vector<vector<int>> ret(N, vector<int>(N, 0));
for(auto [a, b] : EV) if(a != b) ret[a][b] = ret[b][a] = 1;
build(ret);
return 1;
}
