#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));
vector<int> gline(N,-1);
for(int i = 0;i < N;i++) gline[i] = i;
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] == need){
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(gline[i] != i) continue;
cs.clear();
dfs(i,1);
if(cs.size() == 1) continue;
vector<int> cv(cs.begin(),cs.end());
if(!check(cv,1)) return 0;
for(int i = 0;i +1 < cv.size();i++){
answer[cv[i]][cv[i+1]] = 1;
}
for(auto &i:cv) gline[i] = cv[0];
}
// build cycle;
vector<int> gcycle(N,-1);
for(int i = 0;i < N;i++){
if(gcycle[i] != -1) continue;
cs.clear();
dfs(i,2);
vector<int> cv(cs.begin(),cs.end());
set<int> sLine;
for(auto &i:cv) sLine.insert(gline[i]);
if(sLine.size() <= 2) return 0;
// check valid
for(auto &i:cv){
for(auto &j:cv){
if(gline[i] != gline[j] && p[i][j] != 2) return 0;
}
}
vector<int> vLine(sLine.begin(),sLine.end());
for(int i = 0;i < vLine.size();i++){
answer[vLine[i]][vLine[(i+1)%vLine.size()]] = 1;
}
for(auto &i:cv) gcycle[i] = cv[0];
}
// 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;
}
