import java.io.File;
import java.util.Scanner;

public class Graph {
    private static final Scanner scanner = new Scanner(System.in);
    static Scanner fileScanner;
    public static void main(String[] args) {
        int num;
        byte[][] arr;
        System.out.println("124768utyuruyb5y3t34tq35yv54yq45yvq54yq45yq54yvq45yq 5y.");
        System.out.println("Enter type of input." + '\n' + "1 is console input, 0 is file input.");
        boolean chose = choose();
        if (chose) {
            System.out.println("Input size of matrix:");
            num = inputMatrixSize();
            System.out.println("Input matrix elements:");
            arr = inputMatrix(num);
        } else {
            String path = inputFilePath();
            num = inputSizeOfMatrixFromFile(path);
            arr = inputMatrixFile(path, num);
        }
        System.out.println("Input start vertex:");
        int vertex = inputVertex(num);
        System.out.println(BFSGraph(arr,num,vertex));
    }

    private static String BFSGraph(byte[][] matrix, int n, int start) {
        boolean[] boolArr = new boolean[n];
        String output = "BFS: ";
        for (int i = 0; i < n; i++) {
            boolArr[i] = false;
        }
        HMQueue.enqueue(start - 1);
        boolArr[start - 1] = true;
        while (!HMQueue.isEmpty()) {
            output = output + (HMQueue.peek() + 1) + " ";
            for (int i = 0; i < n; i++) {
                if ((!boolArr[i]) && (matrix[HMQueue.peek()][i] == 1)) {
                    HMQueue.enqueue(i);
                    boolArr[i] = true;
                }
            }
            HMQueue.dequeue();
        }
        return output;
    }


    private static boolean choose() {
        int inputNumber = 0;
        boolean isIncorrect;
        final int MIN_NUM = 0;
        final int MAX_NUM = 1;
        do {
            isIncorrect = false;
            try {
                inputNumber = Integer.parseInt(scanner.nextLine());
            } catch (Exception e) {
                isIncorrect = true;
                System.out.println("Please, enter a number.");
            }
            if (!isIncorrect && (inputNumber < MIN_NUM || inputNumber > MAX_NUM)) {
                System.out.println("You are out of input range!");
                isIncorrect = true;
            }
        } while (isIncorrect);
        return inputNumber == 1;
    }

    private static int inputData() {
        int n = 0;
        boolean isIncorrect;
        do {
            isIncorrect = false;
            try {
                n = Integer.parseInt(scanner.nextLine());
            } catch (Exception e) {
                isIncorrect = true;
                System.out.println("Please, enter a integer number:");
            }
        } while (isIncorrect);
        return n;
    }
    private static int inputMatrixElement() {
        boolean isIncorrect;
        int n;
        do {
            n = inputData();
            isIncorrect = false;
            if ( (n != 0) && (n != 1)) {
                isIncorrect = true;
                System.out.println("Only 1 or 0 are valid.");
            }
        } while (isIncorrect);
        return n;
    }

    private static int inputMatrixSize() {
        boolean isIncorrect;
        final int MIN_SIZE = 1;
        final int MAX_SIZE = 10;
        int num;
        do {
            num = inputData();
            isIncorrect = false;
            if ((num < MIN_SIZE) || (num > MAX_SIZE)) {
                System.out.println("Matrix size should be in the range from 1 to 10:");
                isIncorrect = true;
            }
        } while (isIncorrect);
        return num;
    }

    private static int inputVertex(final int MAX_SIZE) {
        boolean isIncorrect;
        final int MIN_SIZE = 1;
        int num;
        do {
            num = inputData();
            isIncorrect = false;
            if ((num < MIN_SIZE) || (num > MAX_SIZE)) {
                System.out.println("Start vertex should exist at least, bro.");
                isIncorrect = true;
            }
        } while (isIncorrect);
        return num;
    }

    private static byte[][] inputMatrix(int num) {
        byte[][] arr = new byte[num][num];
        for (int i = 0; i < arr.length; i++)
            for (int j = 0; j < arr.length; j++)
                arr[i][j] = (byte) inputMatrixElement();
        if (!checkMatrix(arr)){
            System.out.println("bro, input correct matrix");
            inputMatrix(num);
        }
        return arr;
    }
    private static boolean checkMatrix(byte[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j] != matrix[j][i]) return false;
            }
        }
        return true;
    }

    private static String inputFilePath() {
        String path;
        boolean isIncorrect;
        do {
            isIncorrect = false;
            System.out.println("Input file path:");
            path = scanner.nextLine();
            File file = new File(path);
            if (!file.exists()) {
                System.out.println("Wrong way to file.");
                isIncorrect = true;
            }
            if (!file.canRead() && file.exists()) {
                System.out.println("Impossible to read a file.");
                isIncorrect = true;
            }
            if (!file.canWrite() && file.canRead()) {
                System.out.println("Impossible to write a file.");
                isIncorrect = true;
            }
        } while (isIncorrect);
        return path;
    }
    private static int inputSizeOfMatrixFromFile(String path) {
        int num = 0;
        boolean isIncorrect;
        final int MIN = 1;
        final int MAX = 10;
        do {
            isIncorrect = false;
            try {
                fileScanner = new Scanner(new File(path));
                num = fileScanner.nextInt();
            } catch (Exception q) {
                isIncorrect = true;
                System.out.println("Check file.");
                path = inputFilePath();
            }
            if (!isIncorrect && ((num < MIN) || (num > MAX))) {
                isIncorrect = true;
                System.out.println("Array size should be in the range from 1 to 10:");
                path = inputFilePath();
            }
        } while (isIncorrect);
        return num;
    }
    private static boolean checkBinary (int n) {
        return (n == 1) || (n == 0);
    }

    private static byte[][] inputMatrixFile(String path, int num) {
        boolean isIncorrect;
        byte[][] arr = new byte[num][num];
        int n;
        do {
            isIncorrect = false;
            try {
                fileScanner = new Scanner(new File(path));
                fileScanner.nextLine();
                for (int i = 0; (i < arr.length); i++) {
                    for (int j = 0; j < arr.length; j++) {
                        n = fileScanner.nextInt();
                        if (checkBinary(n)) {
                            arr[i][j] = (byte) n;
                        } else {
                            isIncorrect = true;
                            System.out.println("Matrix should consist of ones and zeros only!");
                            path = inputFilePath();
                        }
                    }
                }
                if (!checkMatrix(arr)){
                    System.out.println("bro, input correct matrix");
                    isIncorrect = true;
                    path = inputFilePath();
                }
            } catch (Exception q) {
                isIncorrect = true;
                System.out.println("Reading of array elements failed.");
                path = inputFilePath();
            }
        } while (isIncorrect);
        return arr;
    }
}
----------------------------------------------------------------
class QueueNode {
    int data;
    QueueNode next;
    public QueueNode(int data) {
        this.data = data;
        this.next = null;
    }
}
----------------------------------------------------------------
class HMQueue {
    private static QueueNode tail = null, head = null;

    public static int dequeue() {
        if (head == null) {
            return -1;
        }
        QueueNode temp = head;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return temp.data;
    }

    public static void enqueue(int item) {
        QueueNode node = new QueueNode(item);
        if (head == null) {
            head = node;
        }
        else {
            tail.next = node;
        }
        tail = node;
    }

    public static int peek() {
        if (head == null) {
            return -1;
        }
        return head.data;
    }

    public static boolean isEmpty() {
        return tail == null && head == null;
    }

}