#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "supertrees.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define END '\n'
#define inf 9e18
#define ff first
#define ss second
#define pb push_back
const int maxN = 1000;
int parent[maxN][4], sz[maxN][4];
int find_parent(int a, int con) {
if (parent[a][con] == a) return a;
else return parent[a][con] = find_parent(parent[a][con], con);
}
void merge(int a, int b, int con) {
a = find_parent(a, con);
b = find_parent(b, con);
if (a == b) return;
if (sz[a][con] < sz[b][con]) swap(a, b);
parent[b][con] = a;
sz[a][con] += sz[b][con];
}
bool same_set(int a, int b, int con) {
a = find_parent(a, con);
b = find_parent(b, con);
return a == b;
}
void make_set(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= 3; ++j) {
parent[i][j] = i;
sz[i][j] = 1;
}
}
}
int construct(vvi p) {
int n = p.size();
vvi A(n, vi(n, 0));
make_set(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 1) merge(i, j, p[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int a = find_parent(i, 1), b = find_parent(j, 1);
if (p[i][j] > 1) {
if (a == b) return 0;
merge(a, b, p[i][j]);
}
}
}
// for (int i = 0; i < n; ++i) {
// for (int j = i + 1; j < n; ++j) {
// int cnt = 0;
// int a = find_parent(i, 1), b = find_parent(j, 1);
// for (int k = 1; k <= 3; ++k) {
// cnt += same_set(a, b, k);
// }
// if (cnt > 1) {
// cout << "LOL: " << i << " " << j << " " << cnt << END;
// return 0;
// }
// }
// }
vector<vvi> comps(4, vvi(n));
for (int i = 0; i < n; ++i) {
int c = find_parent(i, 1);
int a = find_parent(c, 2), b = find_parent(c, 3);
if (sz[a][2] > 1 && sz[b][3] > 1) return 0;
if (sz[a][2] == 2) return 0;
if (sz[b][3] > 1 && sz[b][3] < 4) return 0;
comps[1][c].pb(i);
if (c == i)
comps[2][a].pb(i);
if (c == i)
comps[3][b].pb(i);
}
for (int i = 0; i < n; ++i) {
if ((int)comps[1][i].size() <= 1) continue;
for (int j = 1; j < (int)comps[1][i].size(); ++j) {
int a = comps[1][i][j], b = comps[1][i][j - 1];
if (a == b) {
cout << "FUCK";
}
A[a][b] = A[b][a] = 1;
}
}
for (int i = 0; i < n; ++i) {
if ((int)comps[2][i].size() <= 1) continue;
for (int j = 1; j < (int)comps[2][i].size(); ++j) {
int a = comps[2][i][j], b = comps[2][i][j - 1];
if (a == b) {
cout << "DAMN";
}
A[a][b] = A[b][a] = 1;
}
int a = comps[2][i][0], b = comps[2][i].back();
A[a][b] = A[b][a] = 1;
if (a == b) {
cout << "DAMN_ME";
}
}
for (int i = 0; i < n; ++i) {
if ((int)comps[3][i].size() <= 1) continue;
for (int j = 1; j < (int)comps[3][i].size(); ++j) {
int a = comps[3][i][j], b = comps[3][i][j - 1];
if (a == b) {
cout << "WOW";
}
A[a][b] = A[b][a] = 1;
}
int a = comps[3][i][0], b = comps[3][i].back(), c = comps[3][i][1];
if (b == c) {
cout << "WOW_ME";
}
A[a][b] = A[b][a] = 1;
A[b][c] = A[c][b] = 1;
}
build(A);
return 1;
}
