#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
const ll maxn = 1e3+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
int par[maxn][2];
int fin(int a, bool wh){
if (par[a][wh] == a) return a;
return par[a][wh] = fin(par[a][wh], wh);
}
void merg(int a, int b, bool wh){
a = fin(a, wh); b = fin(b, wh);
if (a == b) return;
par[a][wh] = b;
}
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);
answer.push_back(row);
}
REP(i, n) par[i][0] = par[i][1] = i;
REP(i, n){
REP(j, n){
if (i == j && p[i][j] != 1) return 0;
if (p[i][j] == 3) return 0;
if (i != j && p[i][j] >= 1){
merg(i, j, 0);
}
}
}
REP(i, n){
REP(j, n){
bool p1 = (fin(i, 0) == fin(j, 0));
if (p1 != (p[i][j] >= 1)) return 0;
}
}
vector<vector<int>> comps(n);
REP(i, n) comps[fin(i, 0)].pb(i);
vector<vector<int>> trecomps(n);
for (auto vv:comps){
if (SZ(vv) == 0) continue;
int m = SZ(vv);
REP(i, m){
FOR(j, i+1, m){
if (p[vv[i]][vv[j]] == 1) merg(vv[i], vv[j], 1);
}
}
REP(i, m) FOR(j, i+1, m) if ((p[vv[i]][vv[j]] == 1) != (fin(vv[i], 1) == fin(vv[j], 1))) return 0;
REP(i, m){
trecomps[fin(vv[i], 1)].pb(vv[i]);
}
vector<vector<int>> trees;
REP(i, m) if (SZ(trecomps[vv[i]]) >= 1) trees.pb(trecomps[vv[i]]);
if (SZ(trees) == 2) return 0;
int lstid = -1;
for (auto tree:trees){
if (lstid != -1){
answer[tree[0]][lstid] = answer[lstid][tree[0]] = 1;
}
lstid = tree[0];
int lsttreeid = -1;
for (auto v:tree){
if (lsttreeid != -1) answer[lsttreeid][v] = answer[v][lsttreeid] = 1;
lsttreeid = v;
}
}
if (SZ(trees) > 1){
answer[trees[0][0]][lstid] = answer[lstid][trees[0][0]] = 1;
}
}
build(answer);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
