#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
vector<vector<int> > answer;
void add_edge(int x, int y) {
answer[x][y] = 1;
answer[y][x] = 1;
}
void dfs(int cur, vector<vector<int> > &p, int &comp_cnt, vector<int> &comp, vector<int> &poss, int weight, vector<vector<int> > &by_comp) {
comp[cur] = comp_cnt;
by_comp[comp_cnt - 1].pb(cur);
for(int nei : poss) {
if(!comp[nei] && p[cur][nei] == weight) {
dfs(nei, p, comp_cnt, comp, poss, weight, by_comp);
}
}
}
int construct(vector<vector<int> > p) {
n = (int) p.size();
answer.assign(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;
}
}
}
int tree_cnt = 0;
vector<int> which_tree(n, 0);
vector<int> all(n, 0);
for(int i = 0; i < n; i++) {
all[i] = i;
}
vector<vector<int> > by_tree(n, vector<int> (0, 0));
for(int cur : all) {
if(!which_tree[cur]) {
tree_cnt++;
dfs(cur, p, tree_cnt, which_tree, all, 1, by_tree);
}
}
by_tree.resize(tree_cnt);
vector<int> rep(n, -1);
vector<int> list_reps;
for(vector<int> &tree : by_tree) {
list_reps.pb(tree[0]);
for(int &cur : tree) {
rep[cur] = tree[0];
}
for(int i = 0; i + 1 < (int) tree.size(); i++) {
add_edge(tree[i], tree[i + 1]);
}
for(int x : tree) {
for(int y : tree) {
if(x != y && p[x][y] != 1) {
return 0;
}
}
}
}
for(int x = 0; x < n; x++) {
for(int y = 0; y < n; y++) {
if(p[x][y] != p[rep[x]][rep[y]]) {
return 0;
}
}
}
int cycle_cnt = 0;
vector<int> which_cycle(n, 0);
vector<vector<int> > by_cycle(n, vector<int> (0, 0));
for(int cur : list_reps) {
if(!which_cycle[cur]) {
cycle_cnt++;
dfs(cur, p, cycle_cnt, which_cycle, list_reps, 2, by_cycle);
}
}
by_cycle.resize(cycle_cnt);
for(vector<int> &cycle : by_cycle) {
if((int) cycle.size() == 2) {
return 0;
}
for(int i = 0; i + 1 < (int) cycle.size(); i++) {
add_edge(cycle[i], cycle[i + 1]);
}
add_edge(cycle.back(), cycle[0]);
for(int x : cycle) {
for(int y : cycle) {
if(x != y && p[x][y] != 2) {
return 0;
}
}
}
}
build(answer);
return 1;
}
