#include<bits/stdc++.h>
#include"supertrees.h"
#define rep(i,a,b) for(int i=a;i<int(b);i++)
#define rrep(i,a,b)for(int i=a;i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto& a: v)
typedef long long ll;
using namespace std;
const long long inf = 1e15;
vector<ll> p(2001);
vector<ll> Rank(2001);
ll Ufindset(ll i) {
if (p[i] == i)return i;
return p[i] = Ufindset(p[i]);
}
void UjoinSet(ll i, ll j) {
ll si = Ufindset(i);
ll sj = Ufindset(j);
if (sj == si)return;
if (Rank[sj] > Rank[si])swap(sj, si);
p[sj] = si;
if (Rank[sj] == Rank[si]) Rank[si]++;
}
void print(vector<ll> v) {
trav(a, v)cout << a << " ";
cout << endl;
}
int construct(vector<vector<int>> v) {
rep(i, 0, 2001)p[i] = i;
vector<vector<int>> b(v.size(), vector<int>(v.size()));
rep(i, 0, v.size()) {
ll root = p[i];
ll last = i;
ll two = 0;
rep(j, 0, v.size()) {
if (v[i][j] == 3)return 0;
if (v[i][j]) {
if (v[i][j] == 2) {
p[p[i]] = i;
p[i] = i;
two++;
}
else if (v[i][j] == 1)UjoinSet(i, j);
}
}
}
rep(i, 0, v.size()) Ufindset(i);
rep(i, 0, v.size()) {
ll last = i;
rep(j, 0, v.size()) {
if (i == j)continue;
if (v[i][j]) {
if (v[i][j]==1) {
if (p[i] == i) {
UjoinSet(last, j);
b[last][j] = 1;
b[j][last] = 1;
}
last = j;
}
}
}
}
rep(i, 0, v.size()) {
ll last = i;
ll two = 0;
rep(j, 0, v.size()) {
Ufindset(j);
if (i == j)continue;
if (v[i][j]) {
if (p[j] != j) {
if (p[j] != p[i]) {
if (v[p[i]][p[j]] != v[i][j])return 0;
}
}
}
else if (p[j] == p[i]) return 0;
if (p[i] == i) {
if (p[j] == j) {
if (v[i][j] == 2) {
two++;
UjoinSet(last, j);
b[last][j] = 1;
b[j][last] = 1;
last = j;
}
}
}
}
if (p[i]==i&&two) {
if (two == 1)return 0;
if (p[i] == i) {
UjoinSet(last, i);
b[last][i] = 1;
b[i][last] = 1;
}
}
}
build(b);
return 1;
}
