Connect cities

import sys

class City:
    def __init__(self):
        self.connected = []
        self.been = False

    def connect(self, other):
        self.connected.append(other)
        other.connected.append(self)

    def visit_group(self):
        if self.been:
            return
        self.been = True
        for c in self.connected:
            c.visit_group()

n, m = [int(i) for i in input().split()]
cities = [City() for _ in range(n)]
sys.setrecursionlimit(n + 100)

for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    cities[a].connect(cities[b])

groups = []
for i in range(n):
    if not cities[i].been:
        groups.append(i)
        cities[i].visit_group()

print(len(groups) - 1)
for i in range(1, len(groups)):
    print(groups[0] + 1, groups[i] + 1)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED