#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0;
auto bfs = [&](int allow) {
vector<int> in_comp(n, -1);
vector<vector<int>> comps;
int cur_comp = 0;
for (int i = 0; i < n; i++) {
if (in_comp[i] != -1) continue;
vector<int> comp_element;
queue<int> bfs;
bfs.push(i);
while (!bfs.empty()) {
int u = bfs.front();
bfs.pop();
if (in_comp[u] != -1) continue;
in_comp[u] = cur_comp;
comp_element.push_back(u);
for (int j = 0; j < n; j++) {
if ((allow>>p[i][j])&1) bfs.push(j);
}
}
comps.push_back(comp_element);
cur_comp++;
}
return make_pair(in_comp, comps);
};
auto [chain_id, chains] = bfs(2);
auto [cycle_id, cycles] = bfs(4);
for (vector<int> chain : chains) {
for (int i = 0; i < (int)chain.size()-1; i++) {
answer[chain[i]][chain[i+1]] = answer[chain[i+1]][chain[i]] = 1;
for (int j = 0; j < (int)chain.size(); j++) {
if (p[chain[i]][chain[j]] != 1) return 0;
}
}
}
for (vector<int> cycle : cycles) {
vector<int> subchains;
for (int i : cycle) subchains.push_back(chain_id[i]);
sort(subchains.begin(), subchains.end());
subchains.resize(unique(subchains.begin(), subchains.end()) - subchains.begin());
if (subchains.size() == 1) continue;
if (subchains.size() == 2) return 0;
for (int i = 0; i < (int)subchains.size(); i++) {
int cur = subchains[i], nxt = subchains[(i+1)%subchains.size()];
answer[chains[cur][0]][chains[nxt][0]] = answer[chains[nxt][0]][chains[cur][0]] = 1;
}
}
build(answer);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
