Fragile network

n = int(input())

neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    neighbors[a].append(b)
    neighbors[b].append(a)

root = 1
while len(neighbors[root]) == 1:
    root += 1

leaves = []
visited = [False] * (n + 1)
visited[root] = True
stack = [root]

while stack:
    u = stack.pop()
    if len(neighbors[u]) == 1:
        leaves.append(u)
    for v in neighbors[u]:
        if not visited[v]:
            visited[v] = True
            stack.append(v)

count = len(leaves)
half = count // 2
k = (count + 1) // 2

print(k)
for i in range(k):
    print(leaves[i], leaves[i + half])

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

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED