Connect cities

n,m = map(int,input().split())
k=[-1]*(n+1)

for t in range(m):
    a,b = map(int,input().split())
    while k[a]>=0:
        a=k[a]
    while k[b]>=0:
        b=k[b]
    if a!=b:
        if k[a]<k[b]: 
            a,b=b,a
        k[b]= k[b]+ k[a]
        k[a]=b
s=[]
for j in range(1,n):
    a=j
    b=j+1
    while k[a]>=0:
        a=k[a]
        
    while k[b]>=0:
        b=k[b]
        
    if a!=b:
        if k[a]<k[b]:
            a,b=b,a
            
        k[b]=k[b]+k[a]
        k[a]=b
        s.append((j,j+1))
        
print(len(s))
for u,v in s:
    print(u,v)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED