#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
typedef pair<int, int> pii;
#define SZ(x) ((int) (x.size()))
#define fi first
#define se second
const int N = 2222;
int n;
int vis[N];
int root[N];
vector<vector<int>> p, b;
vector<int> roots, t;
void add(int u, int v) {
b[u][v] = b[v][u] = 1;
}
void dfs(int u) {
t.push_back(u);
vis[u] = 1;
for(int v = 0; v < n; ++v) {
if(u == v || vis[v] || p[u][v] != 1)
continue;
dfs(v);
}
}
void rec(int u) {
vis[u] = true;
t.push_back(u);
for(int v: roots) {
if(p[u][v] == 2 && !vis[v]) {
rec(v);
}
}
}
int construct(vector<vector<int>> _p) {
p = _p;
n = p.size();
b = vector<vector<int>>(n, vector<int>(n, 0));
// Last subtask
for(auto& a: p)
for(auto& b: a)
if(b == 3)
return 0;
for(int foo = 0; foo < n; foo++) {
if(vis[foo])
continue;
t.clear();
dfs(foo);
for(int i: t) {
for(int j = 0; j < n; ++j) {
if(p[i][j] != p[t[0]][j]) {
return 0;
}
}
}
// Can name anyone the root since they all the same
for(int i = 0; i + 1 < SZ(t); ++i) {
add(t[i], t[i + 1]);
root[t[i + 1]] = t[0];
}
roots.push_back(t[0]);
}
printf("Roots=%d\n", SZ(roots));
memset(vis, 0, sizeof vis);
for(int u: roots) {
if(vis[u])
continue;
t.clear();
rec(u);
if(SZ(t) == 2)
return 0;
if(SZ(t) == 1)
continue;
for(int x: t)
for(int y: t)
if(x != y && p[x][y] != 2)
return 0;
for(int i = 0; i < SZ(t); ++i) {
add(t[i], t[(i+1)%SZ(t)]);
}
}
build(b);
return 1;
}
