#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1e3 + 5;
vector <int> graph[2][SIZE];
int answer[SIZE][SIZE];
bitset <SIZE> been;
int cc_head[SIZE], cc_cnt[SIZE];
vector <int> cc;
void get_cc(int nd, int tp){
if(been[nd])
return;
been[nd] = 1;
cc.push_back(nd);
for(auto i:graph[tp][nd]){
get_cc(i, tp);
}
return;
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if(p[i][j])
graph[p[i][j] - 1][i].push_back(j);
}
}
for (int i = 0; i < n; i++){
if(!been[i]){
cc.clear();
get_cc(i, 0);
for(auto u:cc){
cc_head[u] = i;
for (auto v : cc){
if(p[u][v] != 1)
return 0;
}
}
for (int j = 0; j + 1 < cc.size(); j++){
answer[cc[j]][cc[j + 1]] = 1;
answer[cc[j + 1]][cc[j]] = 1;
}
cc_cnt[i] = cc.size();
}
}
been.reset();
for (int i = 0; i < n; i++){
if(!been[i]){
cc.clear();
get_cc(i, 1);
set<int> st;
for (auto u : cc){
st.insert(cc_head[u]);
for (auto v : cc){
if(p[u][v] == 0)
return 0;
}
}
int tmp = 0;
for (auto j : st){
tmp += cc_cnt[j];
}
if(tmp != cc.size())
return 0;
for (auto j = st.begin(); next(j) != st.end(); j = next(j)){
answer[*j][*next(j)] = 1;
answer[*next(j)][*j] = 1;
}
if(st.size() >= 2){
answer[*prev(st.end())][*st.begin()] = 1;
answer[*st.begin()][*prev(st.end())] = 1;
}
}
}
vector<vector<int>> ret;
for (int i = 0; i < n; i++) {
vector<int> row;
for (int j = 0; j < n; j++){
row.push_back(answer[i][j]);
}
ret.push_back(row);
}
build(ret);
return 1;
}
