#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
#define cps2(x, y) sort(all(x), y), (x).erase(unique(all(x)), end(x))
#define mem(x, y) memset(& x, y, sizeof(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 1003;
int n, ans[n0][n0], used[n0], num[n0], k, k2, m, m2, cyc[n0], cn, comp[n0];
bitset <n0> g[n0], has[n0], has2[n0];
string s[n0], s2[n0];
map <string, int> ind, ind2;
int was[n0], good[n0];
vector <int> cycle[n0];
void dfs(int v) {
used[v] = 1, num[v] = k;
for (int to = 0; to < n; to++) {
if (used[to] || !g[v][to]) continue;
dfs(to);
}
}
void go(int v) {
used[v] = 1, comp[v] = k2;
for (int to = 0; to < n; to++) {
if (used[to] || !ans[v][to]) continue;
go(to);
}
}
void add(int x, int y) {
ans[x][y] = ans[y][x] = 1;
}
int construct(vector<vector<int>> p) {
n = p.size();
string emp = "";
for (int i = 0; i < n; i++) emp += '0';
for (int i = 0; i < n; i++) {
s[i] = s2[i] = emp;
for (int j = 0; j < n; j++) {
if (p[i][j] >= 1) g[i][j] = 1;
if (i == j || p[i][j] == 2) s[i][j] = '1';
s2[i][j] = char('0' + p[i][j]);
}
if (!ind.count(s[i])) ind[s[i]] = m++;
has[ind[s[i]]][i] = 1;
if (!ind2.count(s2[i])) ind2[s2[i]] = m2++;
has2[ind2[s2[i]]][i] = 1;
}
bitset <n0> tmp;
mem(num, -1);
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i);
k++;
int flag = 0;
for (int j = 0; j < n; j++) {
if (num[j] == k - 1) {
if (!flag) tmp = g[j], flag = 1;
//else if (tmp != g[j]) return 0;
}
}
}
}
for (int i = 0; i < n; i++) {
int ok = 0;
for (int j = 1; j <= cn; j++) {
int bad = 0;
for (int k : cycle[j])
if (p[i][k] != 2) bad = 1;
if (!bad) {
ok = 1;
cycle[j].pb(i);
break;
}
}
if (!ok) {
cycle[++cn].pb(i);
}
}
for (int i = 1; i <= cn; i++) {
//cerr << "cycle\n";
//for (int j : cycle[i])
//cerr << j << ' ';
//cerr << '\n';
if (SZ(cycle[i]) < 3) continue;
for (int j = 0; j < SZ(cycle[i]); j++) {
cyc[cycle[i][j]] = 1;
//cerr << cycle[i][j] << ' ';
add(cycle[i][j], cycle[i][(j + 1) % SZ(cycle[i])]);
}
}
//cerr << "k\n";
for (auto & cur : ind2) {
//cerr << cur.first << ' ' << cur.second << '\n';
int one = -1;
for (int i = 0; i < n; i++) {
if (cur.first[i] == '1' && cyc[i]) {
if (one == -1) one = i;
else return 0;
}
}
if (one == -1) {
int cnt = 0, last = -1;
for (int i = 0; i < n; i++)
cnt += (cur.first[i] == '1');
for (int i = 0; i < n; i++) {
if (!has2[cur.second][i]) continue;
assert(cur.first[i] != '0');
cnt--;
if (last == -1) last = i;
else {
add(last, i);
}
}
if (cnt != 0) return 0;
continue;
}
int flag = 0;
for (int i = 0; i < n; i++) {
if (!has2[cur.second][i]) continue;
if (one != i) flag = 1;
}
if (!flag) continue;
if (was[one]) return 0;
was[one] = 1;
mem(good, 0);
good[one] = 1;
//cerr << cur.first << ' ' << cur.second << '\n';
for (int i = 0; i < n; i++) {
if (!has2[cur.second][i]) continue;
if (one != i)
add(one, i);
good[i] = 1;
}
for (int i = 0; i < n; i++) {
if (good[i]) continue;
//if (cur.first[i] != '0' && num[i] != num[one]) return 0;
//if (cur.first[i] != '2' && num[i] == num[one]) return 0;
}
}
mem(used, 0);
for (int i = 0; i < n; i++) {
if (!used[i]) {
go(i);
k2++;
}
}
mem(comp, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((comp[i] == comp[j]) != (num[i] == num[j])) return 0;
}
}
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
for (int j = 0; j < n; j++)
if (ans[i][j] || ans[j][i]) row[j] = 1;
answer.push_back(row);
}
build(answer);
return 1;
}
