Connect cities

import java.util.*;

public class ConnectCities {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] graph = new int[n][n];
        
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a - 1][b - 1] = 1;
            graph[b - 1][a - 1] = 1;
        }
        
        int nbRoads = 0;
        List<int[]> citiesToConnect = new ArrayList<>();
        boolean[] visited = new boolean[n];
        Deque<Integer> citiesToVisit = new ArrayDeque<>();
        citiesToVisit.add(0);

        while (containsFalse(visited)) {
            if (!citiesToVisit.isEmpty()) {
                int actualNode = citiesToVisit.poll();
                if (visited[actualNode]) {
                    continue;
                }
                visited[actualNode] = true;
                for (int ind = 0; ind < graph[actualNode].length; ind++) {
                    if (graph[actualNode][ind] == 1 && !visited[ind]) {
                        citiesToVisit.add(ind);
                    }
                }
            } else {
                nbRoads++;
                int cityNoConnect = indexOfFalse(visited);
                int cityConnected = indexOfTrue(visited);
                citiesToConnect.add(new int[]{cityNoConnect + 1, cityConnected + 1});
                graph[cityNoConnect][cityConnected] = 1;
                graph[cityConnected][cityNoConnect] = 1;
                citiesToVisit.add(cityNoConnect);
            }
        }

        System.out.println(nbRoads);
        for (int[] elt : citiesToConnect) {
            System.out.println(elt[0] + " " + elt[1]);
        }
    }

    private static boolean containsFalse(boolean[] array) {
        for (boolean value : array) {
            if (!value) {
                return true;
            }
        }
        return false;
    }

    private static int indexOfFalse(boolean[] array) {
        for (int i = 0; i < array.length; i++) {
            if (!array[i]) {
                return i;
            }
        }
        return -1; // Should not reach here if called correctly
    }

    private static int indexOfTrue(boolean[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i]) {
                return i;
            }
        }
        return -1; // Should not reach here if called correctly
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 7

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 8

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 9

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 10

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 11

Verdict: RUNTIME ERROR

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at ConnectCities.m...

Test 12

Verdict: ACCEPTED