E8

public class Grafy {

        public static int[] bfs(boolean[][] ms, int vrchol) {
                Queue<Integer> rad = new LinkedList<Integer>();
                int[] vysledok = new int[ms.length];
                Arrays.fill(vysledok, -1);
                vysledok[vrchol] = 0;
                rad.offer(vrchol);
                while (!rad.isEmpty()) {
                        vrchol = rad.poll();
                        for (int i = 0; i < ms.length; i++) {
                                if (ms[vrchol][i] && vysledok[i] == -1) {
                                        vysledok[i] = vysledok[vrchol] + 1;
                                        rad.offer(i);
                                }
                        }
                }

                return vysledok;
        }

        public static int[] bfs(boolean[][] ms, int vrchol, int[] hrany) {
                //Arrays.fill(hrany, -1);
                hrany[vrchol] = -1;
                Queue<Integer> rad = new LinkedList<Integer>();
                int[] vysledok = new int[ms.length];
                Arrays.fill(vysledok, -1);
                vysledok[vrchol] = 0;
                rad.offer(vrchol);
                while (!rad.isEmpty()) {
                        vrchol = rad.poll();
                        for (int i = 0; i < ms.length; i++) {
                                if (ms[vrchol][i] && vysledok[i] == -1) {
                                        vysledok[i] = vysledok[vrchol] + 1;
                                        hrany[i] = vrchol;
                                        rad.offer(i);
                                }
                        }
                }

                return vysledok;
        }

        public static int[] komponentyGrafu(boolean[][] ms) {
                int cisloKomponentu = 1;
                int[] komponenty = new int[ms.length];
                Arrays.fill(komponenty, 0);
                for (int i = 0; i < komponenty.length; i++) {
                        if (komponenty[i] == 0) {
                                int[] hodnoty = bfs(ms, i);
                                for (int j = 0; j < hodnoty.length; j++) {
                                        if (hodnoty[j] >= 0) {
                                                komponenty[j] = cisloKomponentu;
                                        }
                                }

                                cisloKomponentu++;
                        }
                }

                return komponenty;
        }

        public static boolean jeSuvisly(boolean[][] ms) {
                int[] hodnoty = bfs(ms, 0);
                for (int i = 0; i < hodnoty.length; i++)
                        if (hodnoty[i] < 0)
                                return false;
                return true;
        }

        public static int[] polomeryVrcholov(boolean[][] ms) {
                int[] vysledok = new int[ms.length];
                for (int i = 0; i < ms.length; i++) {
                        int[] hodnoty = bfs(ms, i);
                        int max = -1;
                        for (int j = 0; j < hodnoty.length; j++) {
                                if (hodnoty[j] > max) {
                                        max = hodnoty[j];
                                }
                        }

                        vysledok[i] = max;
                }
                return vysledok;
        }

        public static int centrumGrafu(boolean[][] ms) {
                if (!jeSuvisly(ms))
                        return -1;

                int centrum = 0;
                int[] polomery = polomeryVrcholov(ms);
                for (int i = 1; i < polomery.length; i++) {
                        if (polomery[i] < polomery[centrum])
                                centrum = i;
                }

                return centrum;
        }

        public static void main(String[] args) {
                boolean[][] ms = nacitajMaticu("graf1");
                //boolean[][] ms = nacitajMaticu("graf2");
                //System.out.println(Arrays.toString(bfs(ms, 0)));
                //System.out.println(Arrays.toString(komponentyGrafu(ms)));
                //System.out.println(Arrays.toString(polomeryVrcholov(ms)));
                System.out.println(centrumGrafu(ms));
        }

        public static boolean[][] nacitajMaticu(String subor) {
                Scanner s = null;
                boolean[][] ms = null;
                try {
                        s = new Scanner(new File(subor));
                        int pocetVrcholov = s.nextInt();
                        ms = new boolean[pocetVrcholov][pocetVrcholov];
                        for (int i = 0; i < pocetVrcholov; i++) {
                                for (int j = 0; j < pocetVrcholov; j++)
                                        ms[i][j] = s.nextInt() == 1;
                        }
                } catch (Exception e) {
                        e.printStackTrace();
                } finally {
                        if (s != null)
                                s.close();
                }

                return ms;
        }
}