#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1e3;
struct DSU{
vector<int> par, sz, trace;
int cnt;
inline DSU(int n){
par.resize(n);
sz.resize(n, 1);
for (int i = 0; i < n; ++i) par[i] = i;
trace.resize(n, -1);
cnt = -1;
}
inline int find(int x){
return (par[x] == x) ? x : (par[x] = find(par[x]));
}
inline void merge(int x, int y){
int u = find(x), v = find(y);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return;
}
inline int order(int x){
int u = find(x);
if (trace[u] == -1)
trace[u] = ++cnt;
return trace[u];
}
};
int construct(vector<vector<int>> p){
int n = p[0].size();
vector<vector<int>> vec(n);
vector<vector<int>> a (n, vector<int> (n, 0));
vector<bool> circle(n, false);
DSU dsu(n);
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
if (p[i][j] != 0) dsu.merge(i, j);
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
return 0;
}
}
for (int i = 0; i < n; ++i)
vec[dsu.order(i)].push_back(i);
int cnt = dsu.cnt;
for (int k = 0; k <= cnt; ++k){
vector<int>& v = vec[k];
vector<int> in;
for (int i : v){
for (int j : v)
if (p[i][j] == 2) circle[i] = true;
if (circle[i]) for (int j : v)
if (p[i][j] == 1 && circle[j]) circle[i] = false;
if (circle[i]) in.push_back(i);
}
if (in.size() > 0 && in.size() <= 2) return 0;
if (in.empty()){
for (int i = 0; i < v.size() - 1; ++i)
a[v[i]][v[i + 1]] = a[v[i + 1]][v[i]] = true;
}
else{
for (int i = 0; i < in.size() - 1; ++i)
a[in[i]][in[i + 1]] = a[in[i + 1]][in[i]] = true;
a[in.back()][in[0]] = a[in[0]][in.back()] = true;
for (int i : in){
int cur = i;
for (int j : v){
if (p[i][j] == 1){
a[cur][j] = a[j][cur] = 1;
cur = j;
}
}
}
}
}
build(a);
return 1;
}
