#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
int par[1005];
int getr(int x){
return (par[x] == x ? x : par[x] = getr(par[x]));
}
void merge(int a, int b){
a = getr(a), b = getr(b);
if(a != b)par[b] = a;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
for(int i=0;i<n;i++)par[i] = i;
std::vector<std::vector<int>> ans;
for (int i = 0; i < n; i++) {
std::vector<int> row(n, 0);
ans.push_back(row);
}
bool f = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j])merge(i, j);
if(p[i][j] == 2)f = 1;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!p[i][j] && getr(i) == getr(j))return 0;
}
}
if(!f){
for(int i=0;i<n;i++){
vector<int> pos;
for(int j=0;j<n;j++)if(getr(j) == i)pos.push_back(j);
for(int j=0;j<(int)pos.size() - 1;j++){
ans[pos[j]][pos[j+1]] = 1;
ans[pos[j+1]][pos[j]] = 1;
}
}
build(ans);
return 1;
}
for(int i=0;i<n;i++){
vector<int> pos;
for(int j=0;j<n;j++)if(getr(j) == i)pos.push_back(j);
if((int)pos.size() == 2)return 0;
for(int j=0;j<(int)pos.size() - 1;j++){
ans[pos[j]][pos[j+1]] = 1;
ans[pos[j+1]][pos[j]] = 1;
}
ans[pos[0]][pos[(int)pos.size() - 1]] = 1;
ans[pos[(int)pos.size() - 1]][pos[0]] = 1;
}
build(ans);
return 1;
}
