#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
private:
vector<int> par, sz;
public:
DisjointSet(int n) {
par = sz = vector<int>(n);
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
int root(int x) {
if (x == par[x]) {
return x;
}
return par[x] = root(par[x]);
}
void join(int a, int b) {
a = root(a);
b = root(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
sz[a] += sz[b];
par[b] = a;
}
bool is_connected(int a, int b) {
return root(a) == root(b);
}
};
const int MAX_N = 1e3 + 5;
vector<vector<int>> g(MAX_N);
vector<int> cnt_two(MAX_N);
bitset<MAX_N> vis;
int construct(vector<vector<int>> mat) {
const int n = (int) mat.size();
DisjointSet DSU(n);
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
cnt += (mat[i][j] == 2);
if (mat[i][j] == 1) {
g[i].emplace_back(j);
}
if (mat[i][j] > 0) {
DSU.join(i, j);
}
}
cnt_two[i] = cnt;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0 && DSU.is_connected(i, j)) {
return 0;
}
}
}
vector<vector<int>> root(MAX_N);
for (int i = 0; i < n; i++) {
root[DSU.root(i)].emplace_back(i);
}
auto add_edge = [&](int st, int et) {
if (st == et) {
return;
}
ans[st][et] = ans[et][st] = 1;
};
auto build_cycle = [&](const vector<int> &arr) {
for (int i = 1; i < (int) arr.size(); i++) {
add_edge(arr[i], arr[i - 1]);
}
add_edge(arr.front(), arr.back());
};
vis.reset();
for (auto to : root) {
if (to.empty()) {
continue;
}
const int sz = (int) to.size();
vector<int> main_cycle;
for (auto cur : to) {
if (cnt_two[cur] == sz - 1) {
main_cycle.emplace_back(cur);
} else {
if (vis[cur]) {
continue;
}
main_cycle.emplace_back(cur);
vis[cur] = true;
vector<int> chain = {cur};
for (auto add : g[cur]) {
assert(vis[add] == false);
vis[add] = true;
add_edge(cur, add);
}
}
}
build_cycle(main_cycle);
}
build(ans);
return 1;
}
