#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
#include "supertrees.h"
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline T range(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const ll INF = 2e18;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e3 + 15;
bitset <N> d[N];
int par[2][N];
int find(int v, int i) {
if(v == par[i][v])
return v;
return par[i][v] = find(par[i][v], i);
}
void unio(int a, int b, int i) {
a = find(a, i);
b = find(b, i);
if(a != b)
par[i][b] = a;
}
bool used[N];
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> row(n, vector <int> (n, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
d[i][j] = p[i][j] != 0;
for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
if(d[i][k])
d[i] |= d[k];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(d[i][j] ^ (p[i][j] != 0))
return 0;
for(int i = 0; i < n; ++i)
par[0][i] = par[1][i] = i;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
if(d[i][j])
unio(i, j, 0);
for(int i = 0; i < n; ++i) {
if(used[i])
continue;
vector <int> cur = {};
for(int j = 0; j < n; ++j)
if(find(i, 0) == find(j, 0))
cur.pb(j);
vector <int> cycle = {};
for(int j = 0; j < cur.size(); ++j) {
int v = cur[j];
if(used[v])
continue;
if(!cycle.empty())
row[cycle.back()][v] = row[v][cycle.back()] = 1;
cycle.pb(v);
used[v] = true;
for(int u : cur) {
if(p[u][v] == 1 && !used[u]) {
used[u] = used[v] = true;
row[u][v] = row[v][u] = 1;
unio(v, u, 1);
v = u;
}
}
}
if(cycle.size() > 1)
row[cycle[0]][cycle.back()] = row[cycle.back()][cycle[0]] = 1;
}
for(int i = 0; i < n; ++i) {
if(!used[i])
return 0;
for(int j = i + 1; j < n; ++j) {
if(p[i][j] == 0 && find(i, 0) != find(j, 0))
continue;
if(p[i][j] == 1 && find(i, 1) == find(j, 1))
continue;
if(p[i][j] == 2 && find(i, 0) == find(j, 0) && find(i, 1) != find(j, 1))
continue;
return 0;
}
}
build(row);
return 1;
}
