Connect cities

import java.util.*;

public class ConnectCities {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();

        List<Connection> newConnections = new ArrayList<>();

        for (int i = 0; i < n-1; i++){
            newConnections.add(new Connection(i+1, i+2));
        }

        List<Integer> oldCons = new ArrayList<>();

        for (int j = 0; j < m; j++){
            int a = input.nextInt();
            int b = input.nextInt();
            int bigger = Math.max(a, b);

            if(!(oldCons.contains(a) && oldCons.contains(b))){

            boolean found = false;
            int i = 0;
            while (i < newConnections.size() && !found){
                 if (newConnections.get(i).b == bigger){
                    newConnections.remove(i);
                    oldCons.add(a);
                    oldCons.add(b);
                    found = true;
                }
                i++;
            }
            i = 0;
            int smaller = Math.min(a, b);
            while (i < newConnections.size() && !found){
                 if (newConnections.get(i).b == smaller){
                    newConnections.remove(i);
                    oldCons.add(a);
                    oldCons.add(b);
                    found = true;
                }
                i++;
            }
            }

        }

        System.out.println(newConnections.size());
        newConnections.forEach(con -> System.out.println(con.a + " " + con.b));
    }

}
class Connection{
    int a;
    int b;
    Connection(int a, int b){
        this.a = a;
        this.b = b;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED