#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 3;
vector<vector<int>> p, answer;
vector<int> adj[N], ans_adj[N], comp;
bool vis[N], c_vis[N];
int cnt[N], n;
void c_dfs(int u, vector<int> &line){
c_vis[u] = true;
line.push_back(u);
for(int to: comp)
if(!c_vis[to] && p[u][to] == 1 && u != to)
c_dfs(to, line);
}
void add_edge(int x, int y){
answer[x][y] = true;
answer[y][x] = true;
ans_adj[x].push_back(y);
ans_adj[y].push_back(x);
}
void solve_comp(){
vector<vector<int>> lines;
for(int i: comp)
if(!c_vis[i]){
lines.push_back({});
c_dfs(i, lines.back());
}
for(auto &line: lines)
for(int i = 0; i < (int)line.size() - 1; ++i)
add_edge(line[i], line[i + 1]);
for(int i = 0; i < (int)lines.size(); ++i)
add_edge(lines[i][0], lines[(i + 1) % lines.size()][0]);
}
void dfs(int u){
vis[u] = true;
comp.push_back(u);
for(int i = 0; i < n; ++i)
if(i != u && p[i][u] && !vis[i])
dfs(i);
}
void valid_dfs(int u){
vis[u] = true;
cnt[u]++;
for(int to: ans_adj[u])
if(!vis[to])
valid_dfs(to);
vis[u] = false;
}
bool valid(){
for(int i = 0; i < n; ++i)
answer[i][i] = 0;
fill(vis, vis + n, 0);
for(int i = 0; i < n; ++i){
fill(cnt, cnt + n, 0);
valid_dfs(i);
for(int j = 0; j < n; ++j)
if(p[i][j] != cnt[j])
return false;
}
return true;
}
void clear(){
fill(vis, vis + n, false);
fill(c_vis, c_vis + n, false);
for(int i = 0; i < n; ++i){
adj[i].clear();
ans_adj[i].clear();
cnt[i] = 0;
}
}
bool solve(){
clear();
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j){
if(p[i][j]){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
for(int i = 0; i < n; ++i)
if(!vis[i]){
comp.clear();
dfs(i);
solve_comp();
}
return valid();
}
int construct(vector<vector<int>> _p) {
p = _p;
n = p.size();
answer.clear();
answer.resize(n, vector<int>(n, 0));
if(solve()){
build(answer);
return 1;
}
return 0;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
/*
2
1 3
3 1
*/
