#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;
class dsu{
public:
vector<int> p, sz;
dsu(int n){
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.resize(n, 1);
}
int get(int x){
return ((x == p[x]) ? x : (p[x] = get(p[x])));
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b)
return false;
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
bool same(int a, int b){
return (get(a) == get(b));
}
};
int construct(vector<vector<int>> p){
int N = SZ(p);
vector<vector<int>> ans(N, vector<int>(N, 0));
dsu a(N), b(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(p[i][j] > 0){
a.unite(i, j);
}
if(p[i][j] > 3){
return 0;
}
}
}
vector<bool> vis(N, false), vis2(N, false);
for(int vroot = 0; vroot < N; vroot++){
int root = a.get(vroot);
if(!vis[root]){
vis[root] = true;
vector<int> vert;
for(int i = 0; i < N; i++){
if(a.same(i, root)){
vert.pb(i);
}
}
bool zero = false, one = true, due = true;
int n = SZ(vert);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[vert[i]][vert[j]] != 2)
due = false;
if(p[vert[i]][vert[j]] != 1)
one = false;
if(p[vert[i]][vert[j]] == 0)
zero = true;
}
}
if(zero == true){
return 0;
}
if(one == true){
for(int i = 1; i < n; i++){
ans[vert[i-1]][vert[i]] = 1;
ans[vert[i]][vert[i-1]] = 1;
}
continue;
}
if(due == true){
if(n < 3)
return false;
for(int i = 1; i < n; i++){
ans[vert[i-1]][vert[i]] = 1;
ans[vert[i]][vert[i-1]] = 1;
}
ans[vert[0]][vert[n-1]] = 1;
ans[vert[n-1]][vert[0]] = 1;
continue;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[vert[i]][vert[j]] == 1){
b.unite(vert[i], vert[j]);
}
}
}
vector<vector<int>> componenti;
for(int i = 0; i < n; i++){
int root = b.get(vert[i]);
vector<int> cur;
for(int j = 0; j < n; j++){
if(b.get(vert[i]) == b.get(vert[j])){
if(p[vert[i]][vert[j]] == 2){
return 0;
}
if(!vis2[root])
cur.pb(vert[j]);
}
}
if(!vis2[root]){
vis2[root] = true;
componenti.pb(cur);
}
}
int sz = SZ(componenti);
if(sz < 3)
return 0;
for(int i = 0; i < sz; i++){
for(int j = 1; j < SZ(componenti[i]); j++){
ans[componenti[i][j-1]][componenti[i][j]] = 1;
ans[componenti[i][j]][componenti[i][j-1]] = 1;
}
}
for(int i = 1; i < sz; i++){
ans[componenti[i-1][0]][componenti[i][0]] = 1;
ans[componenti[i][0]][componenti[i-1][0]] = 1;
}
ans[componenti[sz-1][0]][componenti[0][0]] = 1;
ans[componenti[0][0]][componenti[sz-1][0]] = 1;
}
}
build(ans);
return 1;
}
