#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define lim 1005
vector<int> adj[lim],adj2[lim],arka[lim];
int col[lim],vis[lim],cy[lim];
int vis2[lim],son[lim];
//~ void build(vector<vector<int>> v){
//~ for(auto a:v){
//~ for(auto b:a){
//~ cout<<b<<" ";
//~ }
//~ cout<<'\n';
//~ }
//~ }
inline void dfs(int node,int cur){
vis[node]=1;
col[node]=cur;
for(auto go:adj[node]){
if(vis[go])continue;
dfs(go,cur);
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
vector<vector<int>> benim;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n,0);
cy[i]=0;
answer.push_back(row);
benim.pb(row);
benim[i][i]=1;
for(int j=0;j<n;j++){
if(p[i][j]!=0 && i!=j){
if(p[i][j]==1){adj[i].pb(j);}
}
}
}
int timer=0;
for(int i=0;i<n;i++){
if(vis[i])continue;
dfs(i,++timer);
}
//int stop=1;
for(int i=1;i<=timer;i++){
vector<int> tut;
for(int j=0;j<n;j++){
if(col[j]==i){
tut.pb(j);
}
}
if(tut.size()==1)continue;
for(int j=1;j<(int)tut.size();j++){
int node1=tut[j-1];
int node2=tut[j];
answer[node1][node2]=1;
answer[node2][node1]=1;
vis2[node1]=1;
vis2[node2]=1;
}
for(int j=0;j<tut.size();j++){
for(int k=0;k<tut.size();k++){
if(j==k)continue;
int node1=tut[j];
int node2=tut[k];
benim[node1][node2]=1;
benim[node2][node1]=1;
}
}
cy[tut[0]]=1;
for(int j=1;j<tut.size();j++){
arka[tut[0]].pb(tut[j]);
}
//cout<<tut[0]<<endl;
}
////////////////////////////////
for(int i=0;i<n;i++){
if(cy[i]==0)continue;
vector<int> tut;
tut.pb(i);
for(int j=0;j<n;j++){
if(p[i][j]==2 && (vis2[j]==0 || cy[j])){
tut.pb(j);
cy[j]=0;
vis2[j]=1;
}
}
for(int j=1;j<(int)tut.size();j++){
int node1=tut[j-1];
int node2=tut[j];
answer[node1][node2]=1;
answer[node2][node1]=1;
son[node1]=1;
son[node2]=1;
}
if(tut.size()!=1){
int node1=tut[0];
int node2=tut.back();
answer[node1][node2]=1;
answer[node2][node1]=1;
son[node1]=1;
son[node2]=1;
}
vector<int> ara=tut;
for(auto node:tut){
for(auto gec:arka[node]){
ara.pb(gec);
}
}
for(int j=0;j<ara.size();j++){
for(int k=0;k<ara.size();k++){
if(j==k)continue;
int node1=ara[j];
int node2=ara[k];
//cout<<node1<<" "<<node2<<" "<<
if(col[node1]==col[node2])continue;
benim[node1][node2]=2;
benim[node2][node1]=2;
}
}
}
for(int i=0;i<n;i++){
if(son[i] || vis2[i])continue;
bool ol=1;
for(int j=0;j<n;j++){
if(i==j)continue;
if(p[i][j]==1)ol=0;
}
if(ol==0)continue;
vector<int> tut;
tut.pb(i);
for(int j=0;j<n;j++){
if(i==j || p[i][j]!=2 || vis2[j] || son[j])continue;
tut.pb(j);
}
for(int j=1;j<(int)tut.size();j++){
int node1=tut[j-1];
int node2=tut[j];
answer[node1][node2]=1;
answer[node2][node1]=1;
son[node1]=1;
son[node2]=1;
}
if(tut.size()!=1){
int node1=tut[0];
int node2=tut.back();
answer[node1][node2]=1;
answer[node2][node1]=1;
son[node1]=1;
son[node2]=1;
}
for(int j=0;j<tut.size();j++){
for(int k=0;k<tut.size();k++){
if(j==k)continue;
int node1=tut[j];
int node2=tut[k];
benim[node1][node2]=2;
benim[node2][node1]=2;
}
}
}
int stop=1;
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<n;j++){
//~ cout<<benim[i][j]<<" ";
//~ if(benim[i][j]!=p[i][j])stop=0;
//~ }
//~ cout<<endl;
//~ }
if(stop)build(answer);
return 1;
}
//~ int main(){
//~ int n;cin>>n;
//~ vector<vector<int>> gec;
//~ FOR{
//~ vector<int> tt;
//~ for(int j=0;j<n;j++){
//~ int x;cin>>x;
//~ tt.pb(x);
//~ }
//~ gec.pb(tt);
//~ }
//~ construct(gec);
//~ }
