#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 3;
int parent[MAX_N];
int find(int x) {
return parent[x] = (parent[x] == x ? x : find(parent[x]));
}
void connect(int a, int b) {
if (rand() % 2) swap(a, b);
parent[find(a)] = find(b);
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
parent[i] = i;
}
vector<vector<int>> result(n);
fill(result.begin(), result.end(), vector<int>(n));
if (n == 1) {
build(result);
return 1;
}
bool valid = true;
for (int i = 0; i < n; i++) {
if (!valid) break;
for (int j = 0; j < n; j++) {
if (p[i][j]) {
if (find(i) == find(j)) continue;
connect(i, j);
result[i][j] = 1;
result[j][i] = 1;
} else {
if (find(i) == find(j)) {
valid = false;
break;
}
}
}
}
if (valid) {
build(result);
}
return valid;
}
// subtask 2
// answer consists of a set of different paths
// since p[i][j] is 0 or 1 all pairs with a 1 are
// part of the same component
// also need to check if impossible now
// we do two passes
// first build UFDS
// then check if UFDS holds
