#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));
// build cycle;
int gt = 0;
vector<int> group(N,-1);
set<int> cs;
function<void(int,int)> dfs = [&](int cur,int need){
cs.insert(cur);
for(int nxt = 0;nxt < N;nxt++){
if(nxt == cur) continue;
if(cs.count(nxt)) continue;
if(p[nxt][cur] == 2){
dfs(nxt,need);
}
}
};
auto check = [&](vector<int> &v,int need){
for(auto &i:v){
for(auto &j:v){
if(i == j) continue;
if(p[i][j] != need) return false;
}
}
return true;
};
for(int i = 0;i < N;i++){
if(group[i] != -1) continue;
cs.clear();
dfs(i,2);
if(cs.size() == 1) continue;
if(cs.size() == 2) return 0;
if(cs.size() > 2){
// build a cycle;
vector<int> cv(cs.begin(),cs.end());
if(!check(cv,2)){
return 0;
}
for(auto i:cv) group[i] = gt;
gt++;
for(int i = 0;i < cv.size();i++){
answer[cv[i]][cv[(i+1)%cv.size()]] = 1;
}
}
}
// mirror;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
answer[i][j] |= answer[j][i];
answer[j][i] |= answer[i][j];
}
}
build(answer);
return 1;
}
