#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 4;
bool vis[N];
vector < int > adj[N];
vector < int > par;
vector < vector < int > > np;
int find(int u){
if(par[u] < 0)
return u;
else return par[u] = find(par[u]);
}
void uni(int u, int v){
u = find(u);
v = find(v);
if(u == v)return;
par[u] += par[v];
par[v] = u;
}
void dfs(int s, int u, vector < vector < int > > &ans){
np[s][u]++;
vis[u] = true;
for(auto v : adj[u]){
if(!vis[v])dfs(s, v, ans);
}
vis[u] = false;
}
void create(vector < vector < int > > ans, int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(ans[i][j] > 0){
adj[i].push_back(j);
// adj[j].push_back(i);
}
}
}
for(int u = 0; u < n; u++){
for(int v = 0; v < n; v++)
vis[v] = false;
dfs(u, u, ans);
}
}
void reset_all(int n) {
np.assign(n, vector<int>(n, 0));
par.assign(n, -1);
for(int i = 0; i < n; i++) {
adj[i].clear();
vis[i] = false;
}
}
int construct(vector < vector < int > > p){
int n = p.size();
reset_all(n);
set < int > lnn[n];
vector < int > ln[n];
map < int, map < int , int > > cnt;
for(int i = 0; i < n; i++){
vector < int > v1, v2;
for(int j = 0; j < n; j++){
if(p[i][j] >= 1 && i != j){
uni(i, j);
cnt[i][p[i][j]]++;
if(p[i][j] == 1){
ln[i].push_back(j);
lnn[i].insert(j);
}
}
}
}
set < int > v;
vector < int > g[n];
int q = 0;
for(int i = 0; i < n; i++){
v.insert(find(i));
g[find(i)].push_back(i);
q += ln[i].size() == 0;
}
vector < vector < int > > ans(n, vector < int > (n, 0));
for(auto pre : v){
vector < int > cycle;
for(auto i : g[pre]){
if(cnt[i][2] == g[pre].size() - 1)
cycle.push_back(i);
}
for(int i = 0; i < (int)cycle.size() - 1; i++){
int u = cycle[i];
int v = cycle[i + 1];
ans[u][v] = ans[v][u] = 1;
}
// for(auto i : cycle)cout << i << ' ';cout << endl;
map < int , int > vis;
int lst = ((int)cycle.size() == 0 ? -1 : cycle.back());
int bgn = ((int)cycle.size() == 0 ? -1 : cycle.back());
for(auto i : g[pre]){
if(cnt[i][2] == g[pre].size() - 1 || vis[i])
continue;
vector < int > cur = {i};
for(auto j : ln[i]){
cur.push_back(j);
vis[j] = 1;
}
if(bgn == -1)bgn = cur[0];
if(lst != -1)ans[lst][cur[0]] = ans[cur[0]][lst] = 1;
for(int j = 0; j < cur.size() - 1; j++){
int u = cur[j];
int v = cur[j + 1];
ans[u][v] = ans[v][u] = 1;
}
lst = cur[0];
}
if((int)cycle.size() > 0 && lst != cycle[0])
ans[lst][cycle[0]] = ans[cycle[0]][lst] = 1;
else if((int)cycle.size() == 0 && bgn != -1 && lst != -1 && bgn != lst){
ans[bgn][lst] = ans[lst][bgn] = 1;
}
}
if(q == n){
create(ans, n);
bool ok = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
ok &= (p[i][j] == np[i][j]);
}
if(!ok)
return 0;
build(ans);
return 1;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(find(i) != find(j))continue;
if(lnn[i].count(j) || i == j )np[i][j] = 1;
else np[i][j] = 2;
}
}
bool ok = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
ok &= (p[i][j] == np[i][j]);
}
if(!ok)
return 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
np[i][j] = 0;
create(ans, n);
ok = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
ok &= (p[i][j] == np[i][j]);
}
if(!ok)
return 0;
build(ans);
return 1;
}
/*
7
1 1 1 2 2 2 2
1 1 1 2 2 2 2
1 1 1 2 2 2 2
2 2 2 1 2 1 2
2 2 2 2 1 2 1
2 2 2 1 2 1 2
2 2 2 2 1 2 1
*/
