/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const char nl = '\n';
//const int N = 1e5+10;
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
}
/** @return the "representative" node in x's component */
int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
/** @return whether the merge changed connectivity */
bool unite(int x, int y) {
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) { return false; }
parents[y_root] = x_root;
return true;
}
/** @return whether x and y are in the same connected component */
bool connected(int x, int y) { return find(x) == find(y); }
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
DisjointSets tree(n);
vector<vector<int>> ans(n, vector<int> (n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)continue;
if (p[i][j] == 1)tree.unite(i, j);
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (p[i][j] == 0) {
if (tree.connected(i, j))return 0;
}
}
const int N = 1010;
vector<int> g[N];
for (int i = 0; i < n; ++i) {
g[tree.find(i)].push_back(i);
}
for (int i = 0; i < N; ++i) {
if (sz(g[i]) == 2)return 0;
for (int j = 1; j < sz(g[i]); ++j) {
ans[g[i][j]][g[i][j-1]] = 1;
ans[g[i][j-1]][g[i][j]] = 1;
ans[g[i][0]][g[i][sz(g[i])-1]] = 1;
ans[g[i][sz(g[i])-1]][g[i][0]] = 1;
}
}
build(ans);
return 1;
}
//void solve() {
//init(2, {1, 0, 1});
//cout << compare_plants(1, 2);
//}
//int32_t main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//solve();
//return 0;
//}
