#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];
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;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n,0);
cy[i]=0;
answer.push_back(row);
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;
}
cy[tut[0]]=1;
//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;
}
}
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;
}
if(tut.size()!=1){
int node1=tut[0];
int node2=tut.back();
answer[node1][node2]=1;
answer[node2][node1]=1;
}
}
//~ for(int i=0;i<n;i++){
//~ for(int j=i+1;j<n;j++){
//~ if(p[i][j]){
//~ if(col[i]==col[j])continue;
//~ stop=0;
//~ break;
//~ }
//~ else{
//~ if(col[i]==col[j])stop=0;
//~ }
//~ }
//~ }
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);
//~ }
