## Wesley's Anger Contest 6 Problem 5 - Canadian Christmas Cactus

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Java 3.0s
Python 3.0s
Memory limit: 256M
Java 512M
Python 512M

Author:
Problem types

The WAC team is setting up a Christmas tree! However, the usual Christmas tree's design has become monotonous to them. They need something new and different!

Why not use a cactus instead?

You have been assigned the job of transforming the tree into a cactus. A cactus is a connected graph where every edge belongs to at most one cycle. In addition, the graph may not contain self loops or parallel edges.

The Christmas tree currently has branch hooks, which are connected using tree branches. The branch connects two distinct hooks and . You are allowed to add some new tree branches, each connecting two separate hooks.

To make sure you're not slacking off on your task, the WAC team requires you to add as many new tree branches to the cactus as possible. Please determine the maximum number of tree branches you'll need to add, and tell the WAC team where to add each branch!

For this problem, Python users are recommended to use CPython over PyPy.

#### Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

for all

#### Input Specification

The first line will contain an integer , the number of tree hooks on the Christmas tree.

The next lines describe the Christmas tree's structure. Each line will contain integers, and , indicating a connecting tree branch between the hooks and .

#### Output Specification

This problem is graded with a custom checker.

Output on the first line, describing the maximum number of tree branches added to the Christmas tree.

Next, output lines after the first line, describing the newly added edges. Each line should contain integers, and , indicating a new connecting tree branch between the hooks and .

If is maximized and the new edges form any valid cactus graph, you will receive of the points for that test case and a verdict of Accepted. If only is correct, you will receive of the points for that test case and a verdict of Partially Accepted. If is incorrect, you will receive a verdict of Wrong Answer and no additional test cases will be executed for that subtask. The judge will also provide feedback with your verdict for each test case.

Your points for a subtask is equal to the minimum number of points achieved in each test case of that subtask.

#### Sample Input

6
6 4
3 1
3 6
4 5
2 3

#### Sample Output

2
2 1
3 5

#### Sample Explanation

Two new tree branches can be added to the Christmas tree:

1. One branch between hooks and .
2. One branch between hooks and .

This is one of the several valid set of branches you can add to the tree.