Baltic OI '15 P3 - Network

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Baltic Olympiad in Informatics: 2015 Day 1, Problem 3

The government of Byteland has decided that it is time to connect their little country to the Internet, so that all citizens can participate in programming competitions and watch videos of cute cats. When it was time to build the network backbone of the country, they assigned the company Internet Optimists Inc. with connecting all the n computers of Byteland. The connections were made as direct links between pairs of computers in such a way that any pair of computers are connected by a sequence of links.

Byteland is not a rich country by any means, so to minimize costs the network topology was built in the form of a tree (i.e. there are exactly n-1 direct links between computers). Far too late, it was realized that this solution suffers from a serious drawback. If just a single link is broken, the computers of Byteland will be partitioned so that some computers cannot communicate with each other!

To improve the reliability of Byteland's network, it was decided that it should at least tolerate if a single link is broken. Your task is to help Internet Optimists Inc. to improve the network in a cheapest way. Given the network topology of Byteland (i.e. which n-1 pairs of computers are connected by direct links), find the minimum number of links that need to be added so that the network will still be connected if any single link is broken.

Input Specification

The first line of input contains a positive integer n (n \ge 3), the number of computers in Byteland. For simplicity, all computers are numbered from 1 to n. Each of the following n-1 lines contains a pair of integers a and b (1 \le a, b \le n, a \ne b) that describes a direct link between computers a and b.

Output Specification

In the first line of output your program should write an integer k, the minimal number of links that should be added to the network. In each of the following k lines your program should write a pair of integers a and b (1 \le a, b \le n, a \ne b) that denote the numbers of computers that should be connected by a link. The links can be written in any order. If there is more than one solution, your program should output any one of them.


SubtaskConditions (in each test case)Points
1n \le 1018
2n \le 200045
3n \le 500\,00037

Sample Input 1

1 2
2 3
2 4
5 4
6 4

Sample Output 1

1 5
3 6

Explanation for Sample 1

Sample Input 2

1 2
2 3
3 4
4 5
3 6
3 7
3 8

Sample Output 2

1 6
5 7
8 4

Explanation for Sample 2


  • 0
    VincentQu  commented on April 7, 2023, 6:48 p.m.

    For the second sample test case, the extra connections my code outputted were


    6 5

    7 1

    8 7

    Does anyone know why this gives a wa?

    • 0
      Josh  commented on April 8, 2023, 7:47 a.m.

      I think the checker is broken, my code which ACs on another judge WAs here.

      • 1
        BalintR  commented on April 8, 2023, 6:38 p.m.

        The checker has been updated and all submissions rejudged.