import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
public class supertrees {
int construct(int[][] p) {
int n = p.length;
if (areAllOnes(p)) {
return constructForAllOnes(n);
}
if (areAllAtMostOnes(p)) {
return constructForAllAtMostOnes(p, n);
}
if (areAllZeroOrTwo(p)) {
return constructAllZeroOrTwo(p, n);
}
if (areAllAtMostTwo(p)) {
return constructAtMostTwo(p, n);
}
int[][] answer = new int[n][n];
grader.build(answer);
return 1;
}
int constructAtMostTwo(int[][] p, int n) {
int[] comp = new int[n];
Arrays.fill(comp, -1);
int c = 0;
for (int i = 0; i < n; i++) {
if (comp[i] != -1) continue;
comp[i] = c;
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0) {
if (comp[j] != -1) return 0;
comp[j] = c;
}
}
c++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] > 0 && comp[i] != comp[j]) return 0;
if (p[i][j] == 0 && comp[i] == comp[j]) return 0;
}
}
@SuppressWarnings({"rawtypes", "unchecked"})
ArrayList<Integer>[] C = new ArrayList[c];
for (int i = 0; i < c; i++) {
C[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
C[comp[i]].add(i);
}
int[][] b = new int[n][n];
@SuppressWarnings({"rawtypes", "unchecked"})
ArrayList<Integer>[] G = new ArrayList[n];
int[] used = new int[n];
for (int i = 0; i < n; i++) G[i] = new ArrayList<>();
for (int i = 0; i < c; i++) {
if (C[i].size() <= 1) continue;
ArrayList<Integer> nodes = C[i];
for (int nd : nodes) {
for (int j = 0; j < n; j++) {
if (p[nd][j] == 1 && j != nd) {
G[nd].add(j);
}
}
}
ArrayList<Integer> cycle = new ArrayList<>();
ArrayList<ArrayList<Integer>> comps = new ArrayList<>();
for (int nd : nodes) {
if (used[nd] > 0) continue;
ArrayList<Integer> ls = new ArrayList<>();
dfsMakeTree(nd, nd, b, G, used, ls);
comps.add(ls);
for (int x = 0; x < ls.size(); x++) {
for (int y = x + 1; y < ls.size(); y++) {
if (p[ls.get(x)][ls.get(y)] != 1 ||
p[ls.get(y)][ls.get(x)] != 1) return 0;
}
}
cycle.add(nd);
}
if (cycle.size() <= 1) continue;
if (cycle.size() == 2) return 0;
for (int x = 0; x < cycle.size(); x++) {
for (int y = 0; y < cycle.size(); y++) {
if (x == y) continue;
if (p[cycle.get(x)][cycle.get(y)] != 2) return 0;
}
}
for (int x = 0; x < comps.size(); x++) {
ArrayList<Integer> l1 = comps.get(x);
for (int y = x + 1; y < comps.size(); y++) {
ArrayList<Integer> l2 = comps.get(y);
for (int w : l1) {
for (int v : l2) {
if (p[w][v] != 2 || p[v][w] != 2) {
return 0;
}
}
}
}
}
for (int j = 0; j < cycle.size(); j++) {
int x = cycle.get(j), y = cycle.get((j + 1) % cycle.size());
b[x][y] = 1;
b[y][x] = 1;
}
}
grader.build(b);
return 1;
}
void dfsMakeTree(int v, int p, int[][] b, ArrayList<Integer>[] G, int[] used,
ArrayList<Integer> ls) {
if (v != p) {
b[v][p] = 1;
b[p][v] = 1;
}
ls.add(v);
used[v] = 1;
for (int to : G[v]) {
if (to == p || used[to] > 0) continue;
dfsMakeTree(to, v, b, G, used, ls);
}
}
int constructAllZeroOrTwo(int[][] p, int n) {
int[] comp = new int[n];
Arrays.fill(comp, -1);
int c = 0;
for (int i = 0; i < n; i++) {
if (comp[i] != -1) continue;
comp[i] = c;
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0) {
if (comp[j] != -1) return 0;
comp[j] = c;
}
}
c++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] > 0 && comp[i] != comp[j]) return 0;
if (p[i][j] == 0 && comp[i] == comp[j]) return 0;
}
}
@SuppressWarnings({"rawtypes", "unchecked"})
ArrayList<Integer>[] C = new ArrayList[c];
for (int i = 0; i < c; i++) {
C[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
C[comp[i]].add(i);
}
int[][] b = new int[n][n];
for (int i = 0; i < c; i++) {
if (C[i].size() <= 1) continue;
if (C[i].size() == 2) return 0;
for (int j = 1; j < C[i].size() - 1; j++) {
b[C[i].get(j)][C[i].get(j + 1)] = 1;
b[C[i].get(j + 1)][C[i].get(j)] = 1;
}
b[C[i].get(0)][C[i].get(1)] = 1;
b[C[i].get(1)][C[i].get(0)] = 1;
b[C[i].get(0)][C[i].get(C[i].size() - 1)] = 1;
b[C[i].get(C[i].size() - 1)][C[i].get(0)] = 1;
}
grader.build(b);
return 1;
}
boolean areAllAtMostTwo(int[][] p) {
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
if (p[i][j] > 2) return false;
}
}
return true;
}
int constructForAllAtMostOnes(int[][] p, int n) {
int[] comp = new int[n];
int[][] b = new int[n][n];
Arrays.fill(comp, -1);
int c = 0;
for (int i = 0; i < n; i++) {
if (comp[i] != -1) continue;
comp[i] = c;
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0) {
if (comp[j] != -1) return 0;
comp[j] = c;
}
}
c++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] > 0 && comp[i] != comp[j]) return 0;
if (p[i][j] == 0 && comp[i] == comp[j]) return 0;
}
}
@SuppressWarnings({"rawtypes", "unchecked"})
ArrayList<Integer>[] C = new ArrayList[c];
for (int i = 0; i < c; i++) {
C[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
C[comp[i]].add(i);
}
for (int i = 0; i < c; i++) {
for (int j = 0; j < C[i].size() - 1; j++) {
b[C[i].get(j)][C[i].get(j + 1)] = 1;
b[C[i].get(j + 1)][C[i].get(j)] = 1;
}
}
grader.build(b);
return 1;
}
boolean areAllZeroOrTwo(int[][] p) {
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
if (j != i && p[i][j] % 2 == 1) return false;
}
}
return true;
}
boolean areAllAtMostOnes(int[][] p) {
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
if (p[i][j] > 1) return false;
}
}
return true;
}
boolean areAllOnes(int[][] p) {
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
if (p[i][j] != 1) return false;
}
}
return true;
}
int constructForAllOnes(int n) {
int[][] res = new int[n][n];
for (int i = 0; i < n - 1; i++) {
res[i][i + 1] = 1;
res[i + 1][i] = 1;
}
grader.build(res);
return 1;
}
}
/**
10
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
2 2 2 2 2 1 2 2 2 2
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
* */
