#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1004;
vector<int> A[MAX], B[MAX];
struct UF {
int R[MAX];
UF() {
iota(R, R + MAX, 0);
}
int Find(int n) {
if (n == R[n]) return n;
return R[n] = Find(R[n]);
}
void Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return;
R[a] = b;
}
} UF1, UF2;
int construct(vector<vector<int>> P) {
int N = P.size();
for (auto& v : P) for (int n : v) if (n == 3) return 0;
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
if (P[i][j]) UF2.Union(i, j);
if (P[i][j] == 1) UF1.Union(i, j);
}
bool ok = 1;
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
if (UF2.Find(i) != UF2.Find(j)) ok &= (P[i][j] == 0);
else if (UF1.Find(i) != UF1.Find(j)) {
ok &= (P[i][j] == 2);
B[UF2.Find(i)].push_back(UF1.Find(j));
}
else {
ok &= (P[i][j] == 1);
A[UF1.Find(i)].push_back(j);
}
}
if (!ok) return 0;
for (int i = 0; i < N; ++i) {
sort(A[i].begin(), A[i].end());
A[i].erase(unique(A[i].begin(), A[i].end()), A[i].end());
sort(B[i].begin(), B[i].end());
B[i].erase(unique(B[i].begin(), B[i].end()), B[i].end());
}
vector<vector<int>> G(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) {
for (int n : A[i]) G[i][n] = G[n][i] = 1;
if (B[i].empty()) continue;
if (B[i].size() == 2) return 0;
B[i].push_back(i);
for (int j = 0; j < B[i].size(); ++j) {
int a = B[i][j], b = B[i][(j + 1) % B[i].size()];
G[a][b] = G[b][a] = 1;
}
}
for (int i = 0; i < N; ++i) G[i][i] = 0;
build(G);
return 1;
}
