#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;
void build(vector<vector<int>> _b);
const int MAXN = 1e3+100;
int p[MAXN], sz[MAXN];
void init(int n){
iota(p, p+n, 0);
fill(sz, sz+n, 1);
}
int find_parent(int x){
if(x == p[x])
return x;
return p[x] = find_parent(p[x]);
}
bool same_set(int a, int b){
return (find_parent(a) == find_parent(b));
}
void union_set(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
int p2[MAXN], sz2[MAXN];
void init2(int n){
iota(p2, p2+n, 0);
fill(sz2, sz2+n, 1);
}
int find2(int x){
if(x == p2[x])
return x;
return p2[x] = find2(p2[x]);
}
bool same2(int a, int b){
return (find2(a) == find2(b));
}
void union2(int a, int b){
a = find2(a);
b = find2(b);
if(a == b)
return;
if(sz2[a] < sz2[b])
swap(a, b);
p2[b] = a;
sz2[a] += sz2[b];
}
int construct(vector<vector<int>> p){
int N = SZ(p);
init(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(p[i][j] > 0){
union_set(i, j);
}
}
}
vector<vector<int>> ans(N, vector<int>(N, 0));
vector<bool> vis(N, false), vis2(N, false), touse(N, false);
init2(N);
for(int i = 0; i < N; i++){
int v = find_parent(i);
if(!vis[v]){
vis[v] = true;
vector<int> vertici;
vertici.pb(i);
for(int j = i+1; j < N; j++){
if(same_set(i, j)){
vertici.pb(j);
}
}
for(int j = 0; j < SZ(vertici); j++){
for(int k = 0; k < SZ(vertici); k++){
if(p[vertici[j]][vertici[k]] == 0){
return 0;
}
}
}
if(SZ(vertici) == 2 && p[vertici[0]][vertici[1]] >= 2){
return 0;
}
bool onlyone = true;
for(int j = 0; j < SZ(vertici); j++){
for(int k = 0; k < SZ(vertici); k++){
if(p[vertici[j]][vertici[k]] != 1){
onlyone = false;
}
}
}
if(onlyone){
for(int j = 1; j < SZ(vertici); j++){
ans[vertici[j-1]][vertici[j]] = 1;
ans[vertici[j]][vertici[j-1]] = 1;
}
continue;
}
for(int j = 0; j < SZ(vertici); j++){
for(int k = j + 1; k < SZ(vertici); k++){
int v1 = vertici[j], v2 = vertici[k];
if(p[v1][v2] == 1){
union2(v1, v2);
touse[find2(v1)] = true;
}
}
}
vector<set<int>> vs;
for(int j = 0; j < SZ(vertici); j++){
int root = find2(vertici[j]);
if(!touse[root] || vis2[root]) continue;
vis2[root] = true;
set<int> nuovo;
nuovo.insert(vertici[j]);
for(int k = j+1; k < SZ(vertici); k++){
if(same2(vertici[j], vertici[k])){
nuovo.insert(vertici[k]);
}
}
vs.pb(nuovo);
}
set<int> c;
for(auto x : vertici){
int root = find2(x);
if(!vis2[root]){
c.insert(x);
}
}
vector<int> centre;
int last = -1;
for(auto x : c){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
centre.pb(x);
}
for(int index = 0, j = 0; index < SZ(vs); index++){
last = -1;
for(auto x : vs[index]){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
ans[last][centre[0]] = ans[centre[0]][last] = 1;
}
int da, a;
if(!SZ(vs)){
da = *c.begin(), a = *c.rbegin();
} else{
da = *vs[0].rbegin(), a = *c.rbegin();
}
ans[da][a] = ans[a][da] = 1;
}
}
build(ans);
return 1;
}
