#include "supertrees.h"
#include<vector>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
struct DSU{
int n;
vector<int> dsu, sz;
DSU(int _n){
n = _n;
dsu.resize(n + 1);
sz.resize(n + 1);
for(int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
}
int query(int x){
if(x == dsu[x]) return x;
dsu[x] = query(dsu[x]);
return dsu[x];
}
void unite(int a, int b){
a = query(a);
b = query(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
dsu[b] = a;
}
};
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n));
DSU dsu1(n);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(p[i][j] > 0) dsu1.unite(i, j);
if(p[i][j] == 3) return 0;
}
}
vector<vector<int>> comps(n);
for(int i = 0; i < n; i++){
comps[dsu1.query(i)].push_back(i);
}
for(int pa = 0; pa < n; pa++){
if(comps[pa].empty()) continue;
int sz = (int)comps[pa].size();
DSU dsu2(sz);
for(int i = 0; i < sz; i++){
for(int j = i + 1; j < sz; j++){
if(p[comps[pa][i]][comps[pa][j]] == 0) return 0;
if(p[comps[pa][i]][comps[pa][j]] == 1) dsu2.unite(i, j);
}
}
vector<vector<int>> vec(sz);
for(int i = 0; i < sz; i++) vec[dsu2.query(i)].push_back(i);
for(int i = 0; i < sz; i++){
for(int j = 0; j < sz; j++){
if(dsu2.query(i) == dsu2.query(j)){
if(p[comps[pa][i]][comps[pa][j]] != 1) return 0;
}
else{
if(p[comps[pa][i]][comps[pa][j]] != 2) return 0;
}
}
}
vector<int> imp;
for(int i = 0; i < sz; i++){
if(i == dsu2.query(i)) imp.push_back(comps[pa][i]);
else{
int a = comps[pa][dsu2.query(i)], b = comps[pa][i];
ans[a][b] = 1;
ans[b][a] = 1;
}
}
int szz = (int)imp.size();
if(szz > 1){
if(szz == 2) return 0;
for(int i = 0; i < szz - 1; i++){
ans[imp[i]][imp[i + 1]] = 1;
ans[imp[i + 1]][imp[i]] = 1;
}
ans[imp[szz - 1]][imp[0]] = 1;
ans[imp[0]][imp[szz - 1]] = 1;
}
}
build(ans);
return 1;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g grader.cpp supertrees.cpp
