// Source: https://usaco.guide/general/io
#include <iostream> // cin, cout, cerr
#include <vector> // vector
#include <string> // string
#include <set>
#include "supertrees.h"
#define vec vector
#define mod 1000000007
#define For(i,n) for(int i = 0; i < n; i++)
using namespace std;
int komponenty(vec<vec<int>>& p, vec<vec<int>>& comp, vec<int>& t) {
int n = p.size();
vec<int> kde(n, -1);
for (auto i : t) {
int zakl = 0;
if (kde[i] == -1) {
vec<int> s;
s.push_back(i);
comp.push_back(s);
kde[i] = comp.size() - 1;
zakl = 1;
}
int poc = 0;
For(j, n) {
if (p[i][j] == 0) continue;
poc++;
if (kde[j] == -1) {
if (zakl) {
kde[j] = kde[i];
comp[kde[i]].push_back(j);
} else {
return 0;
}
}
if (kde[j] != kde[i]) {
return 0;
}
}
if (poc != comp[kde[i]].size()) return 0;
}
return 1;
}
int construct(vec<vec<int>> p) {
int n = p.size();
vec<vec<int>> odp(n, vec<int>(n));
vec<vec<int>> comp;
vec<int> t;
For(i, n) {
t.push_back(i);
}
cerr << "trolko" << endl;
int da_sa = komponenty(p, comp, t);
For(i, n) {
For(j, n) {
if (p[i][j] == 2) p[i][j] = 0;
}
}
For(i, comp.size()) {
if (comp[i].size() == 1) continue;
vec<vec<int>> comp2;
da_sa = komponenty(p, comp2, comp[i]);
cerr << "comp[" << i << "] ";
for (auto x : comp[i]) cerr << x << ' ';
cerr << endl;
For(j, comp2.size()) {
For(k, comp2[j].size() - 1) {
odp[comp2[j][k]][comp2[j][k+1]] = 1;
odp[comp2[j][k+1]][comp2[j][k]] = 1;
}
int p1 = comp2[j][0];
int p2 = comp2[(j+1) % (comp2.size())][0];
odp[p1][p2] = 1;
odp[p2][p1] = 1;
}
}
build(odp);
return 1;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
*/
