#include "supertrees.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
typedef long double ld;
ll n, k;
vector<vector<int>>a, d;
vector<int>c, fst;
const int INF = 1e9 + 7;
int construct(vector<vector<int>> p) {
n = p.size();
a = p;
c.resize(n, INF);
fst.resize(n, -1);
d.resize(n);
for (int i = 0; i < n; i++) {
d[i].resize(n, 0);
}
bool ent1 = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] != 0 && p[i][j] != 1) {
ent1 = false;
}
}
}
if (ent1) {
int cur = 0;
for (int v = 0; v < n; v++) {
if (c[v] == INF) {
c[v] = cur++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 1) {
if (c[to] != INF && c[to] != c[v]) {
return 0;
}
c[to] = c[v];
}
else {
if (c[to] == c[v])return 0;
}
}
}
for (int v = 0; v < n; v++) {
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v]) {
d[v][to] = d[to][v] = 1;
break;
}
}
}
build(d);
return 1;
}
else {
int cur = 0;
for (int v = 0; v < n; v++) {
if (c[v] == INF) {
c[v] = cur++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 2) {
if (c[to] != INF && c[to] != c[v]) {
return 0;
}
c[to] = c[v];
}
else if (p[v][to] == 0) {
if (c[to] == c[v])return 0;
}
}
}
for (int v = 0; v < n; v++) {
bool ok = false;
if (fst[c[v]] == -1) {
fst[c[v]] = v;
}
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v]) {
d[v][to] = d[to][v] = 1;
ok = true;
break;
}
}
if (!ok) {
int to = fst[c[v]];
if (to != v) {
if (d[to][v] == 1)return 0;
d[to][v] = d[v][to] = 1;
}
}
}
build(d);
return 1;
}
}
