#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n, pa[1005];
vector<pair<int,int>> adj[3];
vector<vector<int>> answer;
int fp(int n) {
if (pa[n] == n) return n;
return pa[n] = fp(pa[n]);
}
void unite(int u, int v) {
int pu = fp(u), pv = fp(v);
if (pu == pv) return;
answer[pu][pv] = 1;
answer[pv][pu] = 1;
pa[pu] = pv;
}
int construct(vector<vector<int>> p) {
n = p.size();
for (int i = 0; i < n; i++) pa[i] = i;
answer.resize(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] > 2) return 0;
adj[p[i][j]].emplace_back(i, j);
}
}
for (auto [u, v] : adj[1]) {
unite(u, v);
}
for (auto [u, v] : adj[2]) {
if (fp(u) == fp(v)) {
return 0;
}
}
vector<int> vv;
for (int i = 0; i < n; i++) vv.push_back(fp(i));
sort(vv.begin(),vv.end());
vv.erase(unique(vv.begin(),vv.end()),vv.end());
for (auto [u, v] : adj[2]) {
int pu = fp(u), pv = fp(v);
if (pu == pv) continue;
pa[pu] = pv;
}
vector<int> lst[1005];
for (auto node : vv) {
lst[fp(node)].emplace_back(node);
}
for (int i = 0; i < n; i++) {
if (lst[i].empty()) continue;
if (lst[i].size() == 2) return 0;
if (lst[i].size() == 1) continue;
int first = lst[i][0];
for (int j = 0; j + 1 < lst[i].size(); j++) {
answer[lst[i][j]][lst[i][j+1]] = 1;
answer[lst[i][j+1]][lst[i][j]] = 1;
}
answer[first][lst[i][lst[i].size()-1]] = 1;
answer[lst[i][lst[i].size()-1]][first] = 1;
}
for (auto [u, v] : adj[0]) {
if (fp(u) == fp(v)) return 0;
}
build(answer);
return 1;
}
