import java.util.stream.IntStream;

public class Solution {
    
    public static int[] solution(int[][] m) {
        double[][] matrix = new double[m.length][m.length];  //A, assume square matrix as stated

        //find terminal layers
        int[] sums = new int[m.length];  //stored for later use
        int firstTerminal = m.length;

        for (int i = 0; i < m.length; i++) {
            sums[i] = IntStream.of(m[i]).sum();
            if (sums[i] != 0) {  //only normalize for non terminal states
                for (int j = 0; j < m[0].length; j++) {
                    matrix[i][j] = m[i][j] / (double) sums[i];
                }
            } else {
                firstTerminal--;
            }
        }
        
        //exceptional case return
        
        if(sums[0] == 0) {  //s0 is terminal; cannot reach all other states
            int[] fin = new int[m.length + 1];
            fin[0] = fin[m.length] = 1;
            return fin;
        }
        
        //continue computing
        
        int pointer = 0;
        //move terminal states to the end
        for (int i = 0; i < m.length; i++) {
            if (sums[i] == 0) {
                boolean swapped = false;
                int origPos =(int) matrix[i][0];  //store orig pos in first cell of terminal vector since its unused anyways
                if(origPos == 0) origPos = ++pointer;
                
                for (int j = i + 1; j < m.length; j++) {
                    if (sums[j] != 0) { //find earliest non terminal state to swap place
                        sums[i] = sums[j];  //update sums
                        sums[j] = 0;
                        
                        for (int k = 0; k < m.length; k++) {
                            matrix[i][k] = matrix[j][k];  //swap row
                            matrix[j][k] = 0;  //always zero in terminal state vector
                        }
                        
                        for (int k = 0; k < m.length; k++) {
                            double temp = matrix[k][i];
                            matrix[k][i] = matrix[k][j];  //swap column
                            matrix[k][j] = temp;
                        }
                        
                        matrix[j][0] = origPos;
                        swapped = true;
                        break;
                    }
                }
                                    
                if(!swapped) matrix[i][0] = origPos;  //if not swapped, its original
            }
        }

        int qSize = firstTerminal;

        for (int i = 0; i < qSize; i++) {  // I - Q, where Q is sub square matrix of A in the non terminal region
            for (int j = 0; j < qSize; j++) {
                matrix[i][j] = (i == j ? 1 : 0) - matrix[i][j];
            }
        }

        //start inversing Q
        double[][] inverse = new double[qSize][qSize];

        //minor and cofactor calculation
        for (int i = 0; i < qSize; i++) {
            for (int j = 0; j < qSize; j++) {
                inverse[i][j] = Math.pow(-1, i + j) * determinant(minor(matrix, i, j, qSize), qSize - 1);
            }
        }

        //swap elements with determinant
        double det = 1 / determinant(matrix, qSize);
        for (int i = 0; i < qSize; i++) {
            for (int j = 0; j <= i; j++) {
                double temp = inverse[i][j];
                inverse[i][j] = inverse[j][i] * det;
                inverse[j][i] = temp * det;
            }
        }

        //multiply inverse Q with terminal state sub matrix
        double[] w = new double[matrix.length - firstTerminal];

        for (int i = 0; i < w.length; i++) {
            double sum = 0;
            for (int k = 0; k < qSize; k++) {
                sum += matrix[k][i + firstTerminal] * inverse[0][k]; //only need first row results
            }
            w[i] = sum;
        }

        //turn into fractions
        int[][] fractions = new int[w.length][2];
        int gcd = 1;
        for (int i = 0; i < fractions.length; i++) {
            int origPos = (int) matrix[i + firstTerminal][0] - 1;  //fetch original pos from matrix
            int[] f = decimalToFraction(w[i]);
            fractions[origPos][0] = f[0];
            fractions[origPos][1] = f[1];
            if (f[1] != 1)  //ignore denominator=1
                gcd = (gcd * f[1]) / gcd(gcd, f[1]);  //LCM
        }

        //get common denominator and populate the final returning array
        int[] finalRes = new int[fractions.length + 1];
        for (int i = 0; i < fractions.length; i++) {
            finalRes[i] = fractions[i][0] * (gcd / fractions[i][1]);
        }
        finalRes[fractions.length] = gcd;
        
        return finalRes;
    }

    /**
     * START MATRIX HELPER METHODS
     * * assumes square matrixes only
     */
    
    private static double determinant(double[][] matrix, int n) {
        if (matrix.length == 1 || n == 1)
            return matrix[0][0];

        double det = 0;
        for (int i = 0; i < n; i++) {
            det += Math.pow(-1, i) * matrix[0][i] * determinant(minor(matrix, 0, i, n), n - 1);
        }

        return det;
    }
    
    private static double[][] minor(double[][] matrix, int row, int column, int n) {
        int size = n - 1;
        double[][] minor = new double[size][size];

        for (int i = 0; i < n; i++) {
            for (int j = 0; i != row && j < n; j++) {
                if (j != column) {
                    minor[i < row ? i : i - 1][j < column ? j : j - 1] = matrix[i][j];
                }
            }
        }

        return minor;
    }

    /**
     * START FRACTION HELPER METHODS
     */
    
    private static final double EPSILON = 1e-6;
    
    private static int[] decimalToFraction(double d) {
        int xF = (int) Math.round(d);
        int yF = 1;
        double error = Math.abs(d - xF);
        for (int y = 2; error > EPSILON; y++) {
            int x = (int) (d * y);
            for (int i = 0; i < 2; i++) {
                double e = Math.abs(d - ((double) x / y));
                if (e < error) {
                    xF = x;
                    yF = y;
                    error = e;
                }
                x++;
            }
        }
        return new int[] { xF, yF };
    }

    private static int gcd(int a, int b) {
        if (a == 0)
            return b;

        return gcd(b % a, a);
    }
}